QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#150846 | #6123. JAG Graph Isomorphism | Sommohito# | WA | 3ms | 9192kb | C++20 | 2.7kb | 2023-08-26 14:01:48 | 2023-08-26 14:01:48 |
Judging History
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