QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#163855 | #6123. JAG Graph Isomorphism | realIyxiang# | WA | 4ms | 33912kb | C++14 | 3.6kb | 2023-09-04 15:53:11 | 2023-09-04 15:53:12 |
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 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 * 3], 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]];
}
// rep(i, 1, num) cout << z[i] << ' '; cout << '\n';
memset(vis, 0, sizeof(vis));
memset(book, 0, sizeof(book));
tp = num = 0, dfs1(1, 1, 0);
// rep(i, 1, num) cout << z[i] << ' '; cout << '\n';
rep(i, 1, num) {
dfs2(1, z[i], 0), T[1].a[++T[1].num] = T[1].hax[z[i]];
}
if(T[0].num != T[1].num) { puts("No"); return 0; }
// rep(i, 1, T[0].num) cout << T[0].a[i].first << ' '; cout << '\n' << '\n';
// rep(i, 1, T[0].num) cout << T[1].a[i].first << ' '; cout << '\n';
rep(i, 1, T[0].num)
s[i] = T[0].a[i], s[i + T[0].num + 1] = s[i + 2 * T[0].num + 1] = T[1].a[i];
s[T[0].num + 1] = make_pair(114514, 1919810);
auto chk = [&](int n) {
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(i >= 2 * n && z[i] == n) return true;
}
return false;
} ;
if(chk(T[0].num)) puts("Yes");
else puts("No");
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 33320kb
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: 4ms
memory: 33904kb
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: 1ms
memory: 32108kb
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: 1ms
memory: 33912kb
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: 0
Accepted
time: 1ms
memory: 33816kb
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:
No
result:
ok answer is NO
Test #6:
score: 0
Accepted
time: 1ms
memory: 30596kb
input:
350 40 299 79 166 204 324 281 292 63 25 326 188 279 70 64 153 145 121 93 188 283 187 339 1 11 10 330 146 124 45 295 65 208 60 131 39 328 21 181 78 276 5 121 62 81 136 248 78 51 115 87 159 346 338 251 133 306 64 298 183 161 42 14 207 5 73 259 89 269 194 334 129 118 82 50 314 246 72 180 68 166 283 249...
output:
Yes
result:
ok answer is YES
Test #7:
score: 0
Accepted
time: 1ms
memory: 32240kb
input:
506 353 288 61 487 475 353 14 427 103 227 280 13 425 238 10 58 173 240 388 498 12 252 260 326 291 385 32 182 429 10 351 88 12 442 449 224 167 14 5 394 133 492 133 447 199 451 220 468 455 10 472 371 128 392 317 240 36 497 144 149 16 224 272 260 260 323 411 297 361 116 494 46 286 116 483 348 96 337 48...
output:
No
result:
ok answer is NO
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 31036kb
input:
971 648 284 474 937 225 857 112 843 534 919 750 195 81 705 20 524 745 818 410 187 591 423 567 536 945 69 166 165 168 536 348 536 466 914 3 37 23 745 952 662 110 873 153 915 398 539 242 291 548 749 881 836 155 503 599 202 836 186 54 589 361 368 690 387 578 65 153 104 284 456 327 802 706 800 153 950 2...
output:
No
result:
wrong answer expected YES, found NO