QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#150846#6123. JAG Graph IsomorphismSommohito#WA 3ms9192kbC++202.7kb2023-08-26 14:01:482023-08-26 14:01:48

Judging History

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

  • [2023-08-26 14:01:48]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:9192kb
  • [2023-08-26 14:01:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#ifdef APURBA
#include "DEBUG_TEMPLATE.h"
#else
#define HERE
#define debug(args...)
#endif
#define ALL(x) x.begin(),x.end()
const int N = 1e5;

vector<int> g[2][N];
int par[2][N];

bool found[2];

bool cycle[2][N];
vector<int> vs[2];
void dfs(int j,int u,int p)
{
//    debug(j,u);
    par[j][u]=p;
    if(found[j]) return ;
    for(int v: g[j][u]) if(v!=p)
    {
        if(found[j]) return ;
        if(par[j][v] == 0)
        {
            dfs(j,v,u);
        }
        else
        {
            debug(u,v);
            int uu=u;
            while(uu!=v)
            {
                vs[j].push_back(uu);
                cycle[j][uu]=1;
                uu=par[j][uu];

            }
            vs[j].push_back(uu);
            cycle[j][uu]=1;
            found[j] =1 ;
        }
    }
}

map<vector<int>, int> mp;

int gt(vector<int> &v)
{
    auto it = mp.find(v);
    if(it!=mp.end()) return it->second;
    mp[v]=mp.size()+1;
    return mp[v];
}

int num(int j,int u,int p)
{
    vector<int> aa;
    for(int v: g[j][u]) if(v!=p  and cycle[v] == 0)
    {
        aa.push_back(num(j,v,u));
    }
    sort(ALL(aa));
    return gt(aa);
}


vector<int> prefix_function(vector<int> s) {
    int n = (int)s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

bool isRot(vector<int> a, vector<int> b)
{
    int n = a.size();
    int m = b.size();
    a.push_back(0);
    for(int i: b) a.push_back(i);
    for(int i: b) a.push_back(i);
    auto p = prefix_function(a);
    for(int i=0;i<m;i++)
        if(p[i+n+1] == n)
            return 1;
    return 0;
}


bool TEST_CASES()
{
    int n;
    cin>>n;
    for(int j=0;j<2;j++)
    for(int i=1;i<=n;i++)
    {
        int u,v;cin>>u>>v;
        g[j][u].push_back(v);
        g[j][v].push_back(u);
    }

    for(int j=0;j<2;j++)
    {
        dfs(j,1,-1);
    }
    if(vs[0].size()!= vs[1].size())
        return 0;

    for(int j=0;j<2;j++)
    {
        for(auto &i: vs[j])
            i=num(j,i,-1);
    }


    return isRot(vs[0],vs[1]);
}


/*
*/

int32_t main()
{
#ifndef APURBA
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    //freopen("input.txt","r",stdin);
    //freopen("out1.txt","w",stdout);
    int t=1;
    //cin>>t;
    while(t--)
    {
        cout<<(TEST_CASES()?"Yes\n":"No\n");
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 8444kb

input:

4
1 2
2 3
2 4
3 4
1 2
1 3
1 4
3 4

output:

Yes

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 2ms
memory: 8856kb

input:

4
1 2
2 3
3 4
1 4
1 2
1 3
1 4
3 4

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 0ms
memory: 8300kb

input:

6
1 2
1 3
2 5
2 6
3 5
4 6
1 5
1 6
2 4
2 5
2 6
3 4

output:

Yes

result:

ok answer is YES

Test #4:

score: 0
Accepted
time: 3ms
memory: 9192kb

input:

903
835 491
695 797
411 56
636 367
122 715
775 564
199 77
31 593
654 460
330 25
555 345
36 527
768 760
378 753
291 51
676 73
227 883
310 389
656 259
603 836
369 901
347 231
543 259
66 772
301 592
711 738
507 499
425 462
27 458
257 328
628 83
184 645
805 495
491 311
635 874
615 259
39 193
715 673
636...

output:

No

result:

ok answer is NO

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 8760kb

input:

700
520 12
414 245
592 324
396 343
365 93
611 99
163 524
327 310
436 373
646 392
642 15
698 393
599 682
427 341
383 14
218 330
453 441
647 223
14 26
36 118
229 27
56 604
497 177
621 352
178 349
372 257
45 533
44 407
110 343
66 468
564 253
200 27
80 62
50 201
130 5
190 12
140 643
635 130
352 465
223 ...

output:

Yes

result:

wrong answer expected NO, found YES