QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#75446#5307. Subgraph Isomorphismteam1377#WA 59ms6812kbC++142.6kb2023-02-05 10:45:312023-10-15 17:24:16

Judging History

你现在查看的是最新测评结果

  • [2023-10-15 17:24:16]
  • 管理员手动重测本题所有提交记录
  • 测评结果：WA
  • 用时：59ms
  • 内存：6812kb
查看
  • [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:45:35]
  • 评测
  • 测评结果：0
  • 用时：87ms
  • 内存：7004kb
查看
  • [2023-02-05 10:45:31]
  • 提交

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()) {
                assert(0);
            } 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 (n & 1) {
                    flag &= hs[0] == hs[1];
                }
                if (flag) {
                    puts("YES");
                } else {
                    puts("NO");
                }
            }
        }
    }
    return 0;
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 6692kb

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: 0
Accepted
time: 49ms
memory: 6712kb

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:

ok 33192 token(s): yes count is 58, no count is 33134

Test #3:

score: 0
Accepted
time: 59ms
memory: 6480kb

input:

40000
9 24
1 4
1 6
1 7
1 9
2 5
2 7
2 8
2 9
3 5
3 7
3 8
3 9
4 6
4 8
4 9
5 6
5 8
5 9
6 7
6 8
6 9
7 8
7 9
8 9
9 21
1 4
1 6
1 7
1 8
2 5
2 7
2 8
2 9
3 5
3 7
3 9
4 6
4 8
4 9
5 6
5 9
6 7
6 8
6 9
7 8
8 9
9 21
1 4
1 6
1 7
1 8
2 5
2 7
2 8
2 9
3 5
3 7
3 9
4 6
4 8
4 9
5 6
5 9
6 7
6 8
6 9
7 8
7 9
9 22
1 4
1 6
1 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 40000 token(s): yes count is 0, no count is 40000

Test #4:

score: 0
Accepted
time: 56ms
memory: 6484kb

input:

40000
9 16
1 4
1 6
1 8
1 9
2 5
2 7
2 8
2 9
3 6
3 7
4 7
5 8
6 9
7 8
7 9
8 9
9 16
1 4
1 6
1 8
1 9
2 5
2 7
2 8
2 9
3 6
3 7
4 7
5 8
5 9
7 8
7 9
8 9
9 16
1 4
1 6
1 8
1 9
2 5
2 7
2 8
2 9
3 6
3 7
4 7
5 8
5 9
6 9
7 8
8 9
9 16
1 4
1 6
1 8
1 9
2 5
2 7
2 8
2 9
3 6
3 7
4 7
5 8
5 9
6 9
7 8
7 9
9 17
1 4
1 6
1 8
1...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 40000 token(s): yes count is 0, no count is 40000

Test #5:

score: 0
Accepted
time: 54ms
memory: 6708kb

input:

40000
9 17
1 5
1 6
1 7
1 8
2 5
2 7
2 9
3 6
3 8
3 9
4 7
4 8
4 9
5 7
5 8
5 9
6 9
9 18
1 5
1 6
1 7
1 8
2 5
2 7
2 9
3 6
3 8
3 9
4 7
4 8
4 9
5 7
5 8
5 9
6 9
8 9
9 18
1 5
1 6
1 7
1 8
2 5
2 7
2 9
3 6
3 8
3 9
4 7
4 8
4 9
5 7
5 8
5 9
6 9
7 9
9 19
1 5
1 6
1 7
1 8
2 5
2 7
2 9
3 6
3 8
3 9
4 7
4 8
4 9
5 7
5 8
5 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 40000 token(s): yes count is 0, no count is 40000

Test #6:

score: 0
Accepted
time: 52ms
memory: 6812kb

input:

40000
9 17
1 5
1 6
1 7
1 8
2 6
2 7
2 8
2 9
3 7
3 9
4 9
5 8
6 7
6 8
6 9
7 9
8 9
9 16
1 5
1 6
1 7
1 8
2 6
2 7
2 8
2 9
3 7
3 9
4 9
5 8
5 9
6 7
6 8
8 9
9 16
1 5
1 6
1 7
1 8
2 6
2 7
2 8
2 9
3 7
3 9
4 9
5 8
5 9
6 7
6 8
7 9
9 17
1 5
1 6
1 7
1 8
2 6
2 7
2 8
2 9
3 7
3 9
4 9
5 8
5 9
6 7
6 8
7 9
8 9
9 17
1 5
1...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 40000 token(s): yes count is 0, no count is 40000

Test #7:

score: 0
Accepted
time: 46ms
memory: 6404kb

input:

40000
9 15
1 5
1 8
1 9
2 6
2 7
2 9
3 6
3 7
4 7
4 8
4 9
5 8
6 9
7 9
8 9
9 13
1 5
1 8
1 9
2 6
2 7
2 9
3 6
3 7
4 7
4 8
4 9
5 8
5 9
9 14
1 5
1 8
1 9
2 6
2 7
2 9
3 6
3 7
4 7
4 8
4 9
5 8
5 9
8 9
9 14
1 5
1 8
1 9
2 6
2 7
2 9
3 6
3 7
4 7
4 8
4 9
5 8
5 9
7 9
9 15
1 5
1 8
1 9
2 6
2 7
2 9
3 6
3 7
4 7
4 8
4 9
5...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 40000 token(s): yes count is 1, no count is 39999

Test #8:

score: -100
Wrong Answer
time: 44ms
memory: 6700kb

input:

40000
9 8
1 9
2 9
3 9
4 9
5 9
6 9
7 9
8 9
9 8
1 8
1 9
2 9
3 9
4 9
5 9
6 9
7 9
9 9
1 8
1 9
2 9
3 9
4 9
5 9
6 9
7 9
8 9
9 8
1 8
2 8
3 9
4 9
5 9
6 9
7 9
8 9
9 8
1 8
1 9
2 8
3 9
4 9
5 9
6 9
7 9
9 9
1 8
1 9
2 8
3 9
4 9
5 9
6 9
7 9
8 9
9 9
1 8
1 9
2 8
2 9
3 9
4 9
5 9
6 9
7 9
9 10
1 8
1 9
2 8
2 9
3 9
4 9
5...

output:

YES
YES
NO
YES
YES
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
N...

result:

wrong answer expected YES, found NO [673rd token]
English 繁體中文 简体中文

服务器时间: 2024-12-03 00:35:57 | 开源项目