QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#150850 | #6123. JAG Graph Isomorphism | Sommohito# | WA | 4ms | 14668kb | C++20 | 2.7kb | 2023-08-26 14:04:43 | 2023-08-26 14:04:45 |
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 = 2e5+5;
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[j][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: 4ms
memory: 14668kb
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: 3ms
memory: 13760kb
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: -100
Wrong Answer
time: 4ms
memory: 13932kb
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:
No
result:
wrong answer expected YES, found NO