QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#75445#5307. Subgraph Isomorphismteam1377#WA 73ms6608kbC++142.5kb2023-02-05 10:43:382023-02-05 10:43:38

Judging History

你现在查看的是测评时间为 2023-02-05 10:43:38 的历史记录

  • [2023-10-15 17:24:16]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:49ms
  • 内存:6600kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-05 10:43:38]
  • 评测
  • 测评结果:0
  • 用时:73ms
  • 内存:6608kb
  • [2023-02-05 10:43:38]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

vector<int> G[N];
vector<int> S, cyc;
int inS[N];

void dfs(int x, int fa = -1)
{
    S.push_back(x);
    inS[x] = 1;
    for (int i = 0; i < G[x].size(); ++i) {
        int v = G[x][i];
        if (v == fa) {
            continue;
        }
        if (inS[v]) {
            int p;
            do {
                p = S.back();
                S.pop_back();
                cyc.push_back(p);
            } while (p != v);
            return;
        }
        dfs(v, x);
        if (cyc.size()) {
            return;
        }
    }
    S.pop_back();
    inS[x] = 0;
    return;
}

int base[N], siz[N];

int hhash(int x, int fa = -1, int fa2 = -1)
{
    siz[x] = 1;
    vector<int> tmp;
    for (int i = 0; i < G[x].size(); ++i) {
        int v = G[x][i];
        if (v == fa || v == fa2) {
            continue;
        }
        tmp.push_back(hhash(v, x));
        siz[x] += siz[v];
    }
    sort(tmp.begin(), tmp.end());
    int val = siz[x];
    for (int i = 0; i < tmp.size(); ++i) {
        val = (1ll * val * base[i] + tmp[i]) % 998244353;
    }
    return val;
}

signed main()
{
    mt19937 rnd;
    for (int i = 0; i < N; ++i) {
        base[i] = rnd() % 998244353;
    }
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) {
            G[i].clear();
            inS[i] = 0;
        }
        for (int i = 1; i <= m; ++i) {
            int x, y;
            scanf("%d%d", &x, &y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
        if (m == n - 1) {
            puts("YES");
        } else if (m != n) {
            puts("NO");
        } else {
            S.clear();
            cyc.clear();
            dfs(1);
            if (!cyc.size()) {
                puts("NO");
            } else {
                vector<int> hs;
                for (int i = 0; i < cyc.size(); ++i) {
                    hs.push_back(hhash(cyc[i], cyc[(i - 1 + cyc.size()) % cyc.size()], cyc[(i + 1) % cyc.size()]));
                }
                int flag = 1;
                for (int i = 2; i < cyc.size(); ++i) {
                    flag &= hs[i] == hs[i - 2];
                }
                if (flag) {
                    puts("YES");
                } else {
                    puts("NO");
                }
            }
        }
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 6608kb

input:

4
7 6
1 2
2 3
3 4
4 5
5 6
3 7
3 3
1 2
2 3
3 1
5 5
1 2
2 3
3 4
4 1
1 5
1 0

output:

YES
YES
NO
YES

result:

ok 4 token(s): yes count is 3, no count is 1

Test #2:

score: -100
Wrong Answer
time: 73ms
memory: 6340kb

input:

33192
2 1
1 2
3 2
1 3
2 3
3 3
1 2
1 3
2 3
4 3
1 4
2 4
3 4
4 3
1 3
1 4
2 4
4 4
1 3
1 4
2 4
3 4
4 4
1 3
1 4
2 3
2 4
4 5
1 3
1 4
2 3
2 4
3 4
4 6
1 2
1 3
1 4
2 3
2 4
3 4
5 4
1 5
2 5
3 5
4 5
5 4
1 4
1 5
2 5
3 5
5 5
1 4
1 5
2 5
3 5
4 5
5 5
1 4
1 5
2 4
3 5
4 5
5 5
1 4
1 5
2 4
2 5
3 5
5 6
1 4
1 5
2 4
2 5
3 ...

output:

YES
YES
YES
YES
YES
NO
YES
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
YES
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

wrong answer expected NO, found YES [374th token]