QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#163726#6123. JAG Graph IsomorphismrealIyxiang#WA 214ms61252kbC++142.9kb2023-09-04 14:35:102023-09-04 14:35:10

Judging History

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

  • [2023-09-04 14:35:10]
  • 评测
  • 测评结果:WA
  • 用时:214ms
  • 内存:61252kb
  • [2023-09-04 14:35:10]
  • 提交

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 = 4e5 + 5;
const int base = 1331; 
const int P1 = 998244353, 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]; 
int n, u, v, tp, cnt, 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; 
        T[o].cir[st[tp]] = 1;  
      }
    }
    --tp; 
  } ;
  dfs1(0, 1, 0); 
  memset(vis, 0, sizeof(vis));
  memset(book, 0, sizeof(book)); 
  tp = 0, dfs1(1, 1, 0); 
  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; }
  function <void(int, int, int)> dfs2 = [&](int o, int u, int f) {
    T[o].sz[u] = 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(T[o].sz[u], pw1[1], P1), P1);
    T[o].hax[u].second = inc(T[o].hax[u].second, mul(T[o].sz[u], pw2[1], P2), P2);
  } ;
  rep(o, 0, 1) rep(i, 1, n) if(T[o].cir[i]) 
    dfs2(o, i, 0), T[o].a[++T[o].num] = T[o].hax[i]; 
  rep(o, 0, 1) sort(T[o].a + 1, T[o].a + T[o].cnt + 1); 
  rep(i, 1, T[0].cnt) if(T[0].a[i] != T[1].a[i]) { 
    puts("No"); return 0;
  }
  puts("Yes"); 
  return 0; 
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 42584kb

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: 5ms
memory: 43128kb

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: 38456kb

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: 7ms
memory: 38152kb

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: 3ms
memory: 38080kb

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: 3ms
memory: 39364kb

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: 0ms
memory: 39800kb

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: 0
Accepted
time: 3ms
memory: 38632kb

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:

Yes

result:

ok answer is YES

Test #9:

score: 0
Accepted
time: 4ms
memory: 39064kb

input:

59
17 6
18 55
16 59
35 1
28 2
41 28
58 30
28 29
21 8
20 10
24 27
13 29
58 26
13 22
12 35
8 13
36 15
1 33
5 16
58 11
16 23
52 45
29 57
16 48
31 38
1 27
17 41
14 37
54 50
13 33
59 27
32 13
2 3
13 26
13 34
41 7
54 1
35 43
3 44
31 18
54 51
35 14
39 59
20 29
34 46
59 56
25 32
12 47
25 6
53 26
29 42
32 55...

output:

No

result:

ok answer is NO

Test #10:

score: 0
Accepted
time: 7ms
memory: 42020kb

input:

286
165 14
142 274
11 169
103 182
219 210
61 78
112 273
176 220
29 5
80 254
228 127
223 198
186 74
218 198
272 157
62 251
210 267
142 84
18 276
124 118
126 286
87 53
43 232
60 282
164 274
137 111
198 104
98 211
42 236
94 54
154 168
202 142
124 107
182 165
20 5
239 230
135 171
184 75
212 273
178 41
2...

output:

Yes

result:

ok answer is YES

Test #11:

score: 0
Accepted
time: 1ms
memory: 38380kb

input:

39
16 15
8 4
15 21
36 26
4 6
30 11
3 36
15 31
33 34
5 36
3 19
28 37
27 36
27 25
29 9
11 1
39 18
3 20
2 5
9 21
7 39
32 27
34 21
17 21
3 29
5 15
15 4
36 12
23 27
2 10
6 38
24 36
35 6
14 22
13 14
11 26
5 39
14 11
15 37
1 37
26 5
37 30
13 9
7 14
10 6
11 28
14 33
35 15
8 11
17 27
31 18
30 15
17 13
16 3
1...

output:

No

result:

ok answer is NO

Test #12:

score: 0
Accepted
time: 6ms
memory: 39668kb

input:

650
4 317
341 320
303 241
537 130
365 247
225 255
646 541
499 123
464 144
161 310
139 209
387 151
435 509
294 531
256 461
276 441
181 165
249 305
229 178
90 84
549 5
456 232
587 326
183 407
540 167
207 564
516 465
463 529
149 30
533 497
246 153
9 461
325 301
606 599
274 48
296 389
101 391
394 628
27...

output:

No

result:

ok answer is NO

Test #13:

score: 0
Accepted
time: 3ms
memory: 42548kb

input:

288
91 109
61 38
71 79
114 201
22 133
200 110
88 53
250 42
195 147
239 266
271 116
83 40
178 21
144 254
18 238
204 89
16 88
118 219
219 116
275 34
76 288
234 248
198 49
228 256
29 27
85 132
163 49
190 144
84 255
65 236
185 162
14 70
243 263
220 234
153 205
187 283
96 221
39 166
199 148
7 265
202 229...

output:

No

result:

ok answer is NO

Test #14:

score: 0
Accepted
time: 91ms
memory: 50656kb

input:

116871
39075 32573
116166 73891
46785 26557
109712 67026
96634 74215
20928 27705
74117 37505
41693 113891
93879 112142
29569 17203
22934 79495
70087 92907
28702 82575
21339 116746
66068 100787
91238 12681
48500 112852
80581 76454
92974 88524
24260 112857
36444 115587
93557 74966
48402 38197
21346 74...

output:

Yes

result:

ok answer is YES

Test #15:

score: 0
Accepted
time: 4ms
memory: 40232kb

input:

5764
735 2245
5261 4983
1720 619
3184 2731
2265 4346
1574 2569
5493 4325
4342 4815
958 1651
1818 4830
4898 3423
5684 265
615 1576
3867 508
3912 1491
2895 3135
2291 455
3531 4583
4149 4638
5625 1899
2053 2323
3786 3186
3267 1392
2842 1627
5757 5201
1162 5081
5476 2077
4033 5656
4592 2643
2746 4512
85...

output:

Yes

result:

ok answer is YES

Test #16:

score: 0
Accepted
time: 21ms
memory: 45184kb

input:

29536
27536 26260
10153 13958
24023 8396
12812 13954
13107 19921
11129 25037
2374 4793
28271 13721
19185 5317
21094 29053
13174 2179
16984 1885
10185 27572
10330 8897
29395 20291
6609 7373
12202 3833
13038 20212
2515 24841
11439 2980
14619 16781
8181 18057
8965 28845
22994 27293
28675 21436
19992 24...

output:

Yes

result:

ok answer is YES

Test #17:

score: 0
Accepted
time: 100ms
memory: 57132kb

input:

165208
73984 74911
137816 51572
101919 670
11442 49473
161121 162594
23452 155347
87190 76918
58502 140135
112901 95605
137460 86254
69964 110530
1464 75732
59633 141728
156583 71372
57210 13672
63130 151423
93050 82426
157597 83800
53310 12654
106236 77296
129602 112230
110840 48564
108727 153700
1...

output:

No

result:

ok answer is NO

Test #18:

score: 0
Accepted
time: 87ms
memory: 54792kb

input:

142678
36083 126449
79407 99265
139071 44450
13153 118675
52986 26655
76115 138059
31514 75257
114550 48160
59787 111382
123300 126840
133984 98478
56133 25184
14209 116943
58293 76570
112975 125137
79515 26183
43334 90762
118048 31514
91708 67838
71253 110197
132723 81682
69695 107391
89547 123688
...

output:

No

result:

ok answer is NO

Test #19:

score: 0
Accepted
time: 27ms
memory: 46536kb

input:

45195
41902 12031
7495 14163
28113 33738
31183 8075
30015 29708
25514 39203
41047 44275
59 20623
22601 17647
5919 38696
2994 35788
7772 1243
15498 16332
23341 7650
39203 34917
25882 24621
22865 16940
18922 10693
12496 6763
20623 35356
38551 697
27074 19867
42844 2534
31118 43276
25815 31183
20794 42...

output:

Yes

result:

ok answer is YES

Test #20:

score: 0
Accepted
time: 7ms
memory: 44072kb

input:

21007
17047 1364
6127 463
9139 7027
4290 17796
16555 2623
568 14105
6420 16830
2656 11336
17486 11771
11259 16896
2656 4272
11969 6127
131 9997
18748 10872
11819 5186
14309 19012
9050 14371
18744 14105
20185 3378
4452 20089
1263 11626
18234 15490
4623 12010
19136 9820
6550 2165
6095 9564
20118 9997
...

output:

No

result:

ok answer is NO

Test #21:

score: 0
Accepted
time: 85ms
memory: 50672kb

input:

107464
76154 10587
35783 74082
1649 62833
60094 58802
9398 26303
7688 42924
8598 67244
21208 4946
98346 84157
68017 22886
35309 3317
58681 42998
35219 65971
19533 62162
101250 18885
94163 43127
79234 100293
27774 28585
32589 79723
59009 60420
46924 20427
96548 35919
79307 23226
73748 45912
45849 406...

output:

Yes

result:

ok answer is YES

Test #22:

score: 0
Accepted
time: 152ms
memory: 58428kb

input:

192707
116571 143455
19475 17085
132054 130807
17931 2944
79824 112544
135126 11421
127572 78348
138239 191752
166625 21157
170366 14014
62357 103408
188682 190397
101424 12084
61521 70883
134768 107733
81064 180439
14750 33242
59796 18422
39368 40410
107914 29864
10107 124368
80687 71335
151286 148...

output:

Yes

result:

ok answer is YES

Test #23:

score: 0
Accepted
time: 58ms
memory: 49032kb

input:

88578
47565 79203
12280 83272
72176 46300
57337 57216
36872 14057
45906 46739
49097 42502
8573 67260
86639 4963
44905 84306
74127 46529
76106 28823
73526 4963
22396 83272
29888 61927
85628 11217
12250 19919
75058 44328
72862 62753
860 65086
72862 8156
42557 59513
34970 58630
52190 77530
23333 47565
...

output:

Yes

result:

ok answer is YES

Test #24:

score: -100
Wrong Answer
time: 214ms
memory: 61252kb

input:

198221
6680 189881
135933 131050
150085 103607
116430 190298
3788 56626
127874 75891
35061 26810
114264 107965
11971 189888
29482 44566
108848 156837
34189 48744
78966 5613
43211 110640
181196 102317
129259 57731
107647 164716
1027 32727
75009 14218
32132 131977
58733 38827
38369 167199
92170 49566
...

output:

Yes

result:

wrong answer expected NO, found YES