QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#163855#6123. JAG Graph IsomorphismrealIyxiang#WA 4ms33912kbC++143.6kb2023-09-04 15:53:112023-09-04 15:53:12

Judging History

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

  • [2023-09-04 15:53:12]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:33912kb
  • [2023-09-04 15:53:11]
  • 提交

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