这题应该模一下啊。long long都存不下

#include <cstdio>
#include <assert.h>
#include <cstring>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

const int MAX_N = 500;
int par[MAX_N];

void init(int n)
{
    for (int i = 0; i < n; i++) {
        par[i] = i;
    }
}

int root(int x)
{
    if (par[x] == x){
        return x;
    }
    return par[x] = root(par[x]);
}

void merge(int x, int y)
{
    par[root(x)] = root(y);
}

bool same(int x, int y)
{
    return root(x) == root(y);
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    init(n * 2);
    int up = n;
    while (m--) {
        int a, b, c, d;
        scanf("%d %d %d %d", &a, &b, &c, &d);
        a--; c--;
        if (!same(a, c) && !same(a, c + n)) {
            up--;
        }
        if (b == d) {
            if (same(a, c + n)) {
                printf("No Answer\n");
                return 0;
            }
            merge(a, c);
            merge(a + n, c + n);
        }
        else {
            if (same(a, c)) {
                printf("No Answer\n");
                return 0;
            }
            merge(a, c + n);
            merge(a + n, c);
        }
    }
    printf("%d\n", 1 << up);
}

0 条评论

目前还没有评论...

信息

ID
1221
难度
6
分类
数据结构 | 并查集 点击显示
标签
(无)
递交数
760
已通过
194
通过率
26%
被复制
3
上传者