QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#163840 | #6123. JAG Graph Isomorphism | realIyxiang# | WA | 8ms | 32760kb | C++14 | 3.3kb | 2023-09-04 15:42:27 | 2023-09-04 15:42:28 |
Judging History
answer
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int N = 2e5 + 5;
const int base = 131;
const int P1 = 1e9 + 9, P2 = 1e9 + 7;
struct Graph {
struct edge { int v, id; } ;
vector <edge> G[N]; int cnt, num, sz[N], cir[N];
pair <int, int> a[N], hax[N];
void add (int u, int v, int id) {
G[u].push_back((edge){v, id});
G[v].push_back((edge){u, id});
}
} T[2];
pair <pair <int, int>, int> tmp[N];
pair <int, int> s[N * 3];
int n, u, v, tp, cnt, num, z[N], pw1[N], pw2[N], st[N], dep[N], vis[N], book[N];
int inc (int a, int b, int P) { return (a += b) >= P ? a - P : a; }
int dec (int a, int b, int P) { return (a -= b) < 0 ? a + P : a; }
int mul (int a, int b, int P) { return 1ll * a * b % P; }
int fpow (int a, int b, int P) { int ans = 1; for ( ; b; a = mul(a, a, P), b >>= 1) if(b & 1) ans = mul(ans, a, P); return ans; }
int main () {
ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
pw1[0] = pw2[0] = 1;
rep(i, 1, n) {
pw1[i] = mul(pw1[i - 1], base, P1);
pw2[i] = mul(pw2[i - 1], base, P2);
}
rep(i, 1, n) cin >> u >> v, T[0].add(u, v, i);
rep(i, 1, n) cin >> u >> v, T[1].add(u, v, i);
function <void(int, int, int)> dfs1 = [&](int o, int u, int f) {
vis[u] = 1, st[++tp] = u, dep[u] = dep[f] + 1;
for (auto e : T[o].G[u]) if(!book[e.id]) {
book[e.id] = 1;
if(!vis[e.v]) dfs1(o, e.v, u);
else if(dep[e.v] < dep[u]) {
for ( ; st[tp] != e.v; --tp) T[o].cir[st[tp]] = 1, z[++num] = st[tp];
T[o].cir[e.v] = 1, z[++num] = e.v;
}
}
--tp;
} ;
function <void(int, int, int)> dfs2 = [&](int o, int u, int f) {
T[o].sz[u] = 1, dep[u] = dep[f] + 1;
for (auto e : T[o].G[u]) if(!T[o].cir[e.v] && e.v != f)
dfs2(o, e.v, u);
cnt = 0;
for (auto e : T[o].G[u]) if(!T[o].cir[e.v] && e.v != f)
tmp[++cnt] = make_pair(T[o].hax[e.v], e.v);
sort(tmp + 1, tmp + cnt + 1);
rep(i, 1, cnt) {
T[o].sz[u] += T[o].sz[tmp[i].second];
T[o].hax[u].first = inc(T[o].hax[u].first,
mul(tmp[i].first.first, pw1[T[o].sz[u]], P1), P1);
T[o].hax[u].second = inc(T[o].hax[u].second,
mul(tmp[i].first.second, pw2[T[o].sz[u]], P2), P2);
}
T[o].hax[u].first = inc(T[o].hax[u].first, mul(dep[u], pw1[1], P1), P1);
T[o].hax[u].second = inc(T[o].hax[u].second, mul(dep[u], pw2[1], P2), P2);
} ;
dfs1(0, 1, 0);
rep(i, 1, num) {
dfs2(0, z[i], 0), T[0].a[++T[0].num] = T[0].hax[z[i]];
}
memset(vis, 0, sizeof(vis));
memset(book, 0, sizeof(book));
tp = num = 0, dfs1(1, 1, 0);
rep(i, 1, num) {
dfs2(1, z[i], 0), T[1].a[++T[1].num] = T[1].hax[z[i]];
}
rep(i, 1, n) rep(j, 0, 1) T[j].cnt += T[j].cir[i];
if(T[0].cnt != T[1].cnt) { puts("No"); return 0; }
rep(i, 1, n)
s[i] = T[0].a[i], s[i + n] = s[i + 2 * n] = T[1].a[i];
auto chk = [&]() {
z[1] = 0, z[0] = -1;
rep(i, 2, n * 3) {
int j = z[i - 1];
for ( ; j != -1 && s[j + 1] != s[i]; j = z[j]) ;
z[i] = j + 1;
if(z[i] == n) return true;
}
return false;
} ;
if(chk()) puts("Yes");
else puts("No");
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 30808kb
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: 8ms
memory: 32760kb
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: 6ms
memory: 31308kb
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