QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#465460	#6666. Graf	PorNPtree	35	80ms	43356kb	C++17	2.0kb	2024-07-06 22:17:41	2024-07-06 22:17:42

Judging History

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

[2024-07-06 22:17:42]
评测

测评结果：35
用时：80ms
内存：43356kb

查看

[2024-07-06 22:17:41]
提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int du[N], ox[N], oy[N], vis[N];
vector<int> G[N], T[N + (N >> 1)];
unordered_map<int, int> M[N];
int vs[N + (N >> 1)], siz[N + (N >> 1)], rt;

void dfsRt(int x, int fa = -1) {
    siz[x] = 1;
    int flg = 1;
    for (auto v : T[x]) if (v != fa && !vs[v]) {
        dfsRt(v, x), siz[x] += siz[v], flg &= (siz[v] <= siz[0] / 2);
    }
    if (flg && siz[0] - siz[x] <= siz[0] / 2) {
        if (rt && rt != x) puts("ne"), exit(0);
        rt = x;
    }
    return;
}

int findRt(int x) {
    rt = 0, siz[0] = siz[x];
    dfsRt(x), dfsRt(rt);
    int c = 0;
    for (auto v : T[rt]) {
        c += (!vs[v]);
        if (!vs[v] && siz[v] != siz[rt] / 3) {
            puts("ne"), exit(0);
        }
    }
    if (c && c != 3) puts("ne"), exit(0);
    return rt;
}

void dfs(int x) {
    vs[x] = 1;
    for (auto v : T[x]) if (!vs[v]) dfs(findRt(v));
}

signed main() {
    int n, m; scanf("%d%d", &n, &m);
    vector<int> V{1}, E{0};
    while (V.back() < n) {
        V.push_back(V.back() * 3), E.push_back(E.back() * 3 + 3);
    }
    if (n != V.back() || m != E.back()) return 0 & puts("ne");
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &ox[i], &oy[i]);
        ++du[ox[i]], ++du[oy[i]];
    }
    for (int i = 1; i <= m; ++i) {
        if (du[ox[i]] > du[oy[i]] || (du[ox[i]] == du[oy[i]] && ox[i] > oy[i])) swap(ox[i], oy[i]);
        G[ox[i]].push_back(oy[i]);
    }
    int s = n;
    for (int i = 1; i <= n; ++i) {
        for (auto v : G[i]) vis[v] = i;
        for (auto v : G[i]) for (auto w : G[v]) if (vis[w] == i) {
            if (M[i][v]++ || M[i][w]++ || M[v][w]++) return 0 & puts("ne");
            ++s;
            T[i].push_back(s), T[s].push_back(i);
            T[v].push_back(s), T[s].push_back(v);
            T[w].push_back(s), T[s].push_back(w);
        }
    }
    if (s != n + m / 3) return 0 & puts("ne");
    siz[1] = n;
    dfs(findRt(1));
    puts("da");
    return 0;
}

源文件, 语言: C++17

详细

Subtask #1:

score: 15

Accepted

Test #1:

score: 15

Accepted

time: 3ms

memory: 28292kb

input:

output:

da

result:

ok single line: 'da'

Test #2:

score: 0

Accepted

time: 4ms

memory: 30328kb

input:

output:

da

result:

ok single line: 'da'

Test #3:

score: 0

Accepted

time: 3ms

memory: 28204kb

input:

output:

ne

result:

ok single line: 'ne'

Test #4:

score: 0

Accepted

time: 0ms

memory: 28236kb

input:

output:

ne

result:

ok single line: 'ne'

Test #5:

score: 0

Accepted

time: 0ms

memory: 28224kb

input:

output:

ne

result:

ok single line: 'ne'

Test #6:

score: 0

Accepted

time: 0ms

memory: 28176kb

input:

output:

ne

result:

ok single line: 'ne'

Test #7:

score: 0

Accepted

time: 3ms

memory: 30288kb

input:

output:

ne

result:

ok single line: 'ne'

Test #8:

score: 0

Accepted

time: 0ms

memory: 30292kb

input:

output:

da

result:

ok single line: 'da'

Test #9:

score: 0

Accepted

time: 3ms

memory: 28236kb

input:

output:

ne

result:

ok single line: 'ne'

Test #10:

score: 0

Accepted

time: 5ms

memory: 28176kb

input:

output:

ne

result:

ok single line: 'ne'

Test #11:

score: 0

Accepted

time: 3ms

memory: 30504kb

input:

output:

ne

result:

ok single line: 'ne'

Test #12:

score: 0

Accepted

time: 6ms

memory: 28168kb

input:

output:

da

result:

ok single line: 'da'

Test #13:

score: 0

Accepted

time: 3ms

memory: 30332kb

input:

output:

ne

result:

ok single line: 'ne'

Test #14:

score: 0

Accepted

time: 0ms

memory: 28244kb

input:

output:

ne

result:

ok single line: 'ne'

Test #15:

score: 0

Accepted

time: 3ms

memory: 30292kb

input:

output:

ne

result:

ok single line: 'ne'

Test #16:

score: 0

Accepted

time: 0ms

memory: 30332kb

input:

output:

ne

result:

ok single line: 'ne'

Test #17:

score: 0

Accepted

time: 8ms

memory: 30548kb

input:

output:

ne

result:

ok single line: 'ne'

Test #18:

score: 0

Accepted

time: 3ms

memory: 28516kb

input:

output:

ne

result:

ok single line: 'ne'

Test #19:

score: 0

Accepted

time: 7ms

memory: 28472kb

input:

output:

ne

result:

ok single line: 'ne'

Test #20:

score: 0

Accepted

time: 4ms

memory: 30336kb

input:

output:

da

result:

ok single line: 'da'

Test #21:

score: 0

Accepted

time: 3ms

memory: 28512kb

input:

output:

ne

result:

ok single line: 'ne'

Test #22:

score: 0

Accepted

time: 8ms

memory: 30560kb

input:

output:

ne

result:

ok single line: 'ne'

Test #23:

score: 0

Accepted

time: 7ms

memory: 28480kb

input:

output:

da

result:

ok single line: 'da'

Test #24:

score: 0

Accepted

time: 4ms

memory: 30296kb

input:

output:

ne

result:

ok single line: 'ne'

Test #25:

score: 0

Accepted

time: 8ms

memory: 28248kb

input:

output:

ne

result:

ok single line: 'ne'

Test #26:

score: 0

Accepted

time: 5ms

memory: 28176kb

input:

output:

ne

result:

ok single line: 'ne'

Test #27:

score: 0

Accepted

time: 4ms

memory: 30524kb

input:

output:

ne

result:

ok single line: 'ne'

Test #28:

score: 0

Accepted

time: 4ms

memory: 30276kb

input:

output:

ne

result:

ok single line: 'ne'

Test #29:

score: 0

Accepted

time: 3ms

memory: 30328kb

input:

output:

ne

result:

ok single line: 'ne'

Test #30:

score: 0

Accepted

time: 0ms

memory: 28188kb

input:

output:

da

result:

ok single line: 'da'

Test #31:

score: 0

Accepted

time: 3ms

memory: 30332kb

input:

output:

da

result:

ok single line: 'da'

Test #32:

score: 0

Accepted

time: 5ms

memory: 30324kb

input:

output:

da

result:

ok single line: 'da'

Test #33:

score: 0

Accepted

time: 0ms

memory: 28292kb

input:

output:

da

result:

ok single line: 'da'

Test #34:

score: 0

Accepted

time: 0ms

memory: 30268kb

input:

output:

da

result:

ok single line: 'da'

Subtask #2:

score: 20

Accepted

Test #35:

score: 20

Accepted

time: 3ms

memory: 28244kb

input:

output:

ne

result:

ok single line: 'ne'

Test #36:

score: 0

Accepted

time: 0ms

memory: 28320kb

input:

output:

ne

result:

ok single line: 'ne'

Test #37:

score: 0

Accepted

time: 0ms

memory: 30304kb

input:

output:

ne

result:

ok single line: 'ne'

Test #38:

score: 0

Accepted

time: 4ms

memory: 28236kb

input:

output:

ne

result:

ok single line: 'ne'

Test #39:

score: 0

Accepted

time: 3ms

memory: 28220kb

input:

output:

ne

result:

ok single line: 'ne'

Test #40:

score: 0

Accepted

time: 5ms

memory: 30532kb

input:

output:

ne

result:

ok single line: 'ne'

Test #41:

score: 0

Accepted

time: 4ms

memory: 30500kb

input:

output:

da

result:

ok single line: 'da'

Test #42:

score: 0

Accepted

time: 4ms

memory: 28416kb

input:

output:

da

result:

ok single line: 'da'

Test #43:

score: 0

Accepted

time: 9ms

memory: 30388kb

input:

output:

ne

result:

ok single line: 'ne'

Test #44:

score: 0

Accepted

time: 0ms

memory: 28432kb

input:

output:

da

result:

ok single line: 'da'

Test #45:

score: 0

Accepted

time: 6ms

memory: 30572kb

input:

output:

ne

result:

ok single line: 'ne'

Test #46:

score: 0

Accepted

time: 3ms

memory: 28244kb

input:

output:

ne

result:

ok single line: 'ne'

Test #47:

score: 0

Accepted

time: 9ms

memory: 28300kb

input:

output:

ne

result:

ok single line: 'ne'

Test #48:

score: 0

Accepted

time: 9ms

memory: 30464kb

input:

output:

da

result:

ok single line: 'da'

Test #49:

score: 0

Accepted

time: 0ms

memory: 28572kb

input:

output:

da

result:

ok single line: 'da'

Test #50:

score: 0

Accepted

time: 0ms

memory: 30728kb

input:

output:

da

result:

ok single line: 'da'

Test #51:

score: 0

Accepted

time: 0ms

memory: 30372kb

input:

output:

ne

result:

ok single line: 'ne'

Test #52:

score: 0

Accepted

time: 4ms

memory: 30444kb

input:

output:

ne

result:

ok single line: 'ne'

Test #53:

score: 0

Accepted

time: 0ms

memory: 28492kb

input:

output:

ne

result:

ok single line: 'ne'

Test #54:

score: 0

Accepted

time: 0ms

memory: 28280kb

input:

output:

ne

result:

ok single line: 'ne'

Test #55:

score: 0

Accepted

time: 7ms

memory: 28216kb

input:

output:

ne

result:

ok single line: 'ne'

Test #56:

score: 0

Accepted

time: 3ms

memory: 28496kb

input:

output:

ne

result:

ok single line: 'ne'

Test #57:

score: 0

Accepted

time: 3ms

memory: 28468kb

input:

output:

da

result:

ok single line: 'da'

Test #58:

score: 0

Accepted

time: 5ms

memory: 28524kb

input:

output:

ne

result:

ok single line: 'ne'

Test #59:

score: 0

Accepted

time: 3ms

memory: 28340kb

input:

output:

ne

result:

ok single line: 'ne'

Test #60:

score: 0

Accepted

time: 0ms

memory: 30292kb

input:

output:

ne

result:

ok single line: 'ne'

Test #61:

score: 0

Accepted

time: 0ms

memory: 30268kb

input:

output:

ne

result:

ok single line: 'ne'

Test #62:

score: 0

Accepted

time: 3ms

memory: 30268kb

input:

output:

ne

result:

ok single line: 'ne'

Test #63:

score: 0

Accepted

time: 0ms

memory: 28244kb

input:

output:

ne

result:

ok single line: 'ne'

Test #64:

score: 0

Accepted

time: 3ms

memory: 28432kb

input:

output:

da

result:

ok single line: 'da'

Test #65:

score: 0

Accepted

time: 0ms

memory: 28468kb

input:

output:

da

result:

ok single line: 'da'

Test #66:

score: 0

Accepted

time: 4ms

memory: 30616kb

input:

output:

da

result:

ok single line: 'da'

Test #67:

score: 0

Accepted

time: 8ms

memory: 28676kb

input:

output:

da

result:

ok single line: 'da'

Test #68:

score: 0

Accepted

time: 4ms

memory: 30448kb

input:

output:

da

result:

ok single line: 'da'

Subtask #3:

score: 0

Wrong Answer

Test #69:

score: 15

Accepted

time: 48ms

memory: 34156kb

input:

177147 265719
79646 110581
42107 166686
174516 92541
11418 84874
89568 79680
101533 167489
143016 26545
83401 102450
122789 91031
140172 64836
143906 82843
45757 98991
164963 130550
33432 152305
80043 16055
49162 39443
59476 89357
146429 111186
99327 115855
166381 89990
91164 139281
121510 124610
16...

output:

ne

result:

ok single line: 'ne'

Test #70:

score: 0

Accepted

time: 55ms

memory: 33576kb

input:

177147 265719
38681 77992
106972 53905
88649 110477
113934 98724
78662 109263
134699 83502
31991 92472
126170 144
119650 132169
84458 92531
24682 66176
131541 177081
97342 131339
103685 102763
130223 36375
142925 66285
105340 117815
111137 162166
43022 15242
120307 54486
78258 164394
52991 104308
65...

output:

ne

result:

ok single line: 'ne'

Test #71:

score: 0

Accepted

time: 80ms

memory: 35104kb

input:

177147 265719
80151 35717
121902 3023
160759 169382
24887 142159
40782 159514
23600 98839
121180 62418
122763 152478
148678 114794
11943 72581
173127 2884
97280 4969
155030 45742
120300 148466
134742 140635
79483 24583
71636 91841
140421 126108
44434 53426
133218 79051
161302 161964
59589 111719
961...

output:

ne

result:

ok single line: 'ne'

Test #72:

score: 0

Accepted

time: 69ms

memory: 42268kb

input:

177147 265719
23535 148931
151961 42693
126734 69633
41675 97286
148290 110970
18165 83792
5192 133074
101128 76523
76671 146056
37165 145496
108304 76746
47477 140906
73419 48220
39470 54859
81251 91381
88943 87801
102113 126514
153800 35348
116125 49494
114248 11690
150336 26095
40669 90388
3210 9...

output:

ne

result:

ok single line: 'ne'

Test #73:

score: 0

Accepted

time: 3ms

memory: 30328kb

input:

177147 265720
170712 62225
99915 128584
115624 72186
110450 90393
65021 158547
110390 161798
28967 132365
78897 47218
68752 69351
40606 17503
79654 32708
98155 146206
156781 52063
126696 159590
11625 167534
29472 10242
143508 43084
154423 175381
150212 141153
5882 3903
142063 39110
158366 31577
2263...

output:

ne

result:

ok single line: 'ne'

Test #74:

score: -15

Wrong Answer

time: 57ms

memory: 38456kb

input:

177147 265719
67351 167238
129901 55608
68480 135374
104799 141169
109735 94431
87690 136110
134896 150128
94005 84319
29006 124099
31988 157247
99008 24808
30090 15310
10480 16443
98191 89543
98109 139907
59896 166679
121226 129438
83139 84515
163834 143237
162513 60464
6858 120706
23808 13193
8871...

output:

ne

result:

wrong answer 1st lines differ - expected: 'da', found: 'ne'

Subtask #4:

score: 0

Wrong Answer

Test #103:

score: 50

Accepted

time: 48ms

memory: 34812kb

input:

177147 265719
132920 57252
64370 50983
162323 103641
126430 64347
64421 107962
35533 30427
171597 160614
120187 121996
103235 117200
122594 156637
121481 108177
115386 6337
28269 153079
43775 171594
164425 165290
59340 170257
20858 74213
162837 103195
171976 121082
68853 33317
152714 8959
47095 9036...

output:

ne

result:

ok single line: 'ne'

Test #104:

score: 0

Accepted

time: 0ms

memory: 28240kb

input:

177147 265720
98251 19107
36929 5082
59297 17482
166275 130189
125119 161493
151977 35937
4540 92380
52037 36475
105282 76892
8397 7997
162679 100647
12685 34568
53625 30405
136245 147693
95596 151955
66119 156086
92822 98840
66600 97472
42324 130091
34459 150929
81661 38148
1174 30859
113776 90353
...

output:

ne

result:

ok single line: 'ne'

Test #105:

score: 0

Accepted

time: 21ms

memory: 30404kb

input:

59049 88572
14041 31673
1168 11350
38714 28802
37877 22048
49987 22707
26786 49980
2818 13974
10003 17358
51907 30794
16816 20935
8685 53622
49148 54509
3371 26238
50806 4657
57731 38759
38131 9810
28974 19191
5485 27763
9140 36793
45914 17712
23433 31979
29334 8721
7313 42734
12130 24011
36906 5164...

output:

ne

result:

ok single line: 'ne'

Test #106:

score: 0

Accepted

time: 57ms

memory: 34888kb

input:

177147 265719
119867 167070
130132 12752
120764 56321
15572 66501
139543 82691
70068 42197
61383 135281
122332 161897
68678 68884
51691 172281
33415 150511
101102 101300
108117 151586
39194 21123
173495 82522
134499 170131
15461 53912
114257 106087
137475 32697
31578 172314
139488 145536
118015 1288...

output:

ne

result:

ok single line: 'ne'

Test #107:

score: 0

Accepted

time: 46ms

memory: 35448kb

input:

177147 265719
32229 30186
75313 76163
111944 168135
43914 37095
22266 44860
166052 93754
169557 55704
108797 163872
45432 112994
80343 100383
110188 66178
135008 105902
155873 72661
44225 151314
2720 88316
66950 133820
20039 85930
91897 17236
40370 91049
112750 27809
48067 13266
126431 53691
127666 ...

output:

ne

result:

ok single line: 'ne'

Test #108:

score: 0

Accepted

time: 38ms

memory: 43356kb

input:

59049 88572
26511 33490
28852 45905
27461 12238
3574 21240
10401 47111
25108 30094
41731 23065
34029 50912
24637 3051
39816 52369
17677 44545
29603 11717
24661 41876
6322 19702
11178 38322
12480 26080
47105 3194
12178 36578
32634 16221
25540 24583
42234 24601
15926 7470
5428 20505
18895 24343
6641 2...

output:

ne

result:

ok single line: 'ne'

Test #109:

score: 0

Accepted

time: 45ms

memory: 35744kb

input:

177147 265719
109974 161035
10257 149062
121470 37587
101821 92037
121099 27132
31616 170660
46299 85346
105465 61610
133310 53913
20419 23471
11021 49161
161237 108062
27418 106411
42549 75808
90998 78111
32550 19003
10562 170797
77403 67800
34756 24189
88268 56154
14749 154026
5889 159314
104655 1...

output:

ne

result:

ok single line: 'ne'

Test #110:

score: 0

Accepted

time: 70ms

memory: 41592kb

input:

177147 265719
108664 58201
64269 6343
120585 157969
151929 136534
168726 15269
25610 60139
11181 158806
139226 97957
107369 141067
135947 160932
162045 50711
105512 5940
172321 5888
7221 99888
120318 20857
24810 151590
135587 8881
143228 24034
6096 39018
73071 58377
173193 124153
97410 69946
74197 7...

output:

ne

result:

ok single line: 'ne'

Test #111:

score: 0

Accepted

time: 55ms

memory: 33872kb

input:

177147 265719
32981 44699
147062 61378
88263 172913
58385 30028
98963 22183
21517 65343
40334 104039
63687 1318
136538 117786
2824 90817
170979 107527
93628 112008
35891 28456
164720 154877
2494 115639
119501 113995
31926 105269
92857 99010
174834 17842
11538 142621
125432 105466
135353 157000
68024...

output:

ne

result:

ok single line: 'ne'

Test #112:

score: 0

Accepted

time: 46ms

memory: 33544kb

input:

177147 265719
167966 17672
92091 174891
69156 176406
144245 124379
124290 42270
59738 92303
86870 83034
79441 52547
15702 45945
164475 43564
132133 61402
27448 122029
45378 131195
35639 152970
550 29347
134069 145338
111946 144913
58629 120345
90261 66787
8482 156139
106048 76828
151397 165340
22520...

output:

ne

result:

ok single line: 'ne'

Test #113:

score: 0

Accepted

time: 2ms

memory: 30332kb

input:

177147 265720
84549 59066
8533 97512
95654 45173
28525 150968
86580 149227
57726 67651
52781 160528
97950 141266
100850 14838
166553 138190
61634 14254
57547 24000
168524 11255
116362 130964
170815 172567
120074 7542
128396 3289
29898 125597
163966 69876
50139 142020
84785 71240
22378 26807
135344 1...

output:

ne

result:

ok single line: 'ne'

Test #114:

score: 0

Accepted

time: 54ms

memory: 36112kb

input:

177147 265719
68898 132920
29665 73506
20531 169214
103475 58989
61733 32239
151574 63398
119411 169525
24793 25207
41292 44383
133706 111802
174419 1600
74876 147063
161499 174674
10278 7799
123599 8481
146302 166032
1313 90856
60646 95512
106779 134984
41603 43637
15001 37449
153582 123699
108004 ...

output:

ne

result:

ok single line: 'ne'

Test #115:

score: 0

Accepted

time: 3ms

memory: 28216kb

input:

59049 88573
48002 20129
7630 33065
13470 58907
56979 49428
24783 51171
35198 55138
26000 13842
56782 34295
54165 5732
52635 46706
40182 1575
48144 56529
25104 1814
30791 45557
24736 48013
51257 51882
26582 54128
26950 47776
18073 51674
24939 54097
24871 44506
23664 28536
3218 34786
44770 14839
46589...

output:

ne

result:

ok single line: 'ne'

Test #116:

score: -50

Wrong Answer

time: 49ms

memory: 34604kb

input:

177147 265719
134788 176770
110415 30012
70814 170685
31716 97968
166427 107186
55319 99947
990 168895
127047 57299
122397 109455
67762 167879
120077 134331
18803 64603
48445 33935
104943 45500
128895 87604
148759 151945
94766 103320
129651 15389
26640 140574
173781 39496
132805 125367
168455 59830
...

output:

ne

result:

wrong answer 1st lines differ - expected: 'da', found: 'ne'