QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#528613 | #6396. Puzzle: Kusabi | megumi# | AC ✓ | 33ms | 29724kb | C++14 | 4.3kb | 2024-08-23 16:53:50 | 2024-08-23 16:53:51 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
inline int read() {
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
f = (c == '-') ? -1 : 1, c = getchar();
while (c >= '0' && c <= '9')
x = x * 10 + c - 48, c = getchar();
return f * x;
}
const int N = 1e5 + 10;
int head[N], cnt;
struct edge {
int to, next;
} edge[N << 2];
void add(int u, int v) {
edge[++cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt;
}
int dep[N], cc[N],
tt[N]; // 每个点的深度 每个点传上来的数据的深度 传上来的数据对应的点的编号
char a[N];
pair<char, int> P[N];
pair<int, int> ans[N];
int tr, mx;
void dfs(int u, int fa) {
dep[u] = dep[fa] + 1;
vector<pair<int, int>> vv[3]; // 分别存子树传上来的长短同
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (v == fa)
continue;
dfs(v, u);
if (!tr)
return;
if (a[v] == 'C')
vv[0].push_back({cc[v], tt[v]});
else if (a[v] == 'D')
vv[1].push_back({cc[v], tt[v]});
else if (a[v] == 'T')
vv[2].push_back({cc[v], tt[v]});
}
if (a[u] == 'C')
vv[0].push_back({dep[u], u});
else if (a[u] == 'D')
vv[1].push_back({dep[u], u});
else if (a[u] == 'T')
vv[2].push_back({dep[u], u});
sort(vv[0].begin(), vv[0].end());
sort(vv[1].begin(), vv[1].end());
sort(vv[2].begin(), vv[2].end());
int len0 = vv[0].size(), len1 = vv[1].size(), len2 = vv[2].size();
int flag = -1;
if ((len0 + len1) % 2 + len2 % 2 == 2) {
tr = 0;
return;
}
if (abs(len0 - len1) >= 2) {
tr = 0;
return;
}
a[u] = '-';
for (int i = 0; i < len2; i += 2) {
if (i == len2 - 1 || vv[2][i].first != vv[2][i + 1].first) {
if (flag != -1) {
tr = 0;
return;
}
flag = i, i--;
continue;
}
ans[++mx] = {vv[2][i].second, vv[2][i + 1].second};
}
if (len2 % 2 == 0 && flag != -1) {
tr = 0;
return;
} else if (flag != -1) {
a[u] = 'T';
cc[u] = vv[2][flag].first;
tt[u] = vv[2][flag].second;
}
if (len0 == len1) {
for (int i = 0; i < len0; i++) {
if (vv[0][i].first <= vv[1][i].first) {
tr = 0;
return;
}
ans[++mx] = {vv[0][i].second, vv[1][i].second};
}
return;
}
if (len0 > len1) { // 长多
int r = 0;
a[u] = 'C';
int flag = len0 - 1;
for (int i = 0; i < len1; i++) {
while (vv[0][r].first <= vv[1][i].first && r < len0) {
flag = r;
r++;
if (r == len0) {
tr = 0;
return;
}
}
ans[++mx] = {vv[0][r].second, vv[1][i].second};
r++;
if (r > len0) {
tr = 0;
return;
}
}
cc[u] = vv[0][flag].first;
tt[u] = vv[0][flag].second;
}
else { // 短多
a[u] = 'D';
int r = len1 - 1, flag = 0;
for (int i = len0 - 1; i >= 0; i--) {
if (r == -1) {
tr = 0;
return;
}
while (vv[0][i].first <= vv[1][r].first) {
flag = r;
r--;
if (r == -1) {
tr = 0;
return;
}
}
ans[++mx] = {vv[0][i].second, vv[1][r].second};
r--;
}
cc[u] = vv[1][flag].first;
tt[u] = vv[1][flag].second;
}
}
signed main() {
int n;
n = read();
string s;
tr = 1;
for (int i = 1; i < n; i++) {
int u = read(), fa = read();
cin >> s;
add(fa, u);
add(u, fa);
a[u] = s[0];
}
dep[1] = 1;
dfs(1, 0);
if (!tr || a[1] != '-')
cout << "NO\n", exit(0);
cout << "YES\n";
for (int i = 1; i <= mx; i++)
cout << ans[i].first << ' ' << ans[i].second << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7956kb
input:
8 2 1 - 3 1 - 4 2 Tong 5 2 Tong 6 3 Duan 7 3 - 8 7 Chang
output:
YES 8 6 4 5
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 2ms
memory: 9760kb
input:
10 2 1 Duan 3 2 Duan 4 2 - 5 4 Chang 6 2 Chang 7 1 Duan 8 6 Tong 9 6 Tong 10 3 Chang
output:
YES 8 9 10 3 6 2 5 7
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 1ms
memory: 9752kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: 0
Accepted
time: 30ms
memory: 14708kb
input:
100000 2 1 Duan 3 1 Duan 4 3 - 5 4 Duan 6 3 - 7 4 Duan 8 4 - 9 8 - 10 7 Duan 11 9 - 12 7 Duan 13 7 Duan 14 8 Duan 15 13 - 16 10 Duan 17 11 Duan 18 12 - 19 1 Duan 20 5 Duan 21 4 Duan 22 14 Duan 23 16 - 24 22 Duan 25 16 Duan 26 13 - 27 13 - 28 17 - 29 5 Duan 30 22 - 31 23 - 32 9 Duan 33 5 - 34 30 Duan...
output:
YES 61327 78961 28763 79617 40169 25684 49361 25045 60228 24156 97603 50185 72206 56901 41848 10579 76635 73900 73042 50152 47346 25325 91464 63312 91034 79886 27084 53651 19389 10551 80157 36927 98200 69283 78977 68167 33135 10332 87866 40003 10826 10300 83126 81993 61240 63025 32742 51469 33688 26...
result:
ok Correct.
Test #5:
score: 0
Accepted
time: 11ms
memory: 12472kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 4 - 7 6 - 8 7 - 9 5 - 10 9 - 11 10 - 12 6 - 13 12 - 14 11 - 15 9 - 16 14 - 17 16 - 18 10 - 19 15 - 20 13 - 21 20 - 22 17 - 23 22 - 24 22 Duan 25 11 - 26 12 - 27 20 - 28 18 - 29 28 - 30 16 - 31 28 - 32 30 - 33 31 - 34 28 - 35 34 - 36 35 - 37 22 - 38 34 - 39 38 - 40 35...
output:
YES 61365 54260 94528 66883 80746 52379 57632 25539 86270 70587 50931 10692 46315 46038 51215 3973 42355 40468 31649 28057 57657 73329 29098 26291 66814 21998 93763 45470 84353 54966 74078 41071 30942 25774 51936 59287 82007 9388 40293 8527 97856 57690 76507 67337 58992 76115 76631 90319 86905 51620...
result:
ok Correct.
Test #6:
score: 0
Accepted
time: 33ms
memory: 11308kb
input:
100000 2 1 - 3 2 - 4 3 Duan 5 4 Chang 6 5 Duan 7 6 Chang 8 7 Duan 9 8 Chang 10 9 Duan 11 10 Chang 12 11 Duan 13 12 Chang 14 12 Duan 15 14 Chang 16 15 Tong 17 15 Tong 18 17 Duan 19 18 Duan 20 19 Chang 21 18 Duan 22 21 Duan 23 18 Chang 24 21 - 25 24 Duan 26 25 Chang 27 26 Duan 28 27 Chang 29 26 Duan 3...
output:
YES 37 31 42 40 68 64 180 173 196 150 820 771 777 744 809 803 810 799 778 552 556 528 446 374 423 345 920 772 708 570 510 524 652 649 610 588 682 660 433 397 587 396 503 291 686 641 645 549 536 529 478 429 348 321 294 286 323 284 316 282 307 279 376 341 530 501 1160 1152 1757 1446 1685 1435 1413 142...
result:
ok Correct.
Test #7:
score: 0
Accepted
time: 19ms
memory: 10720kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 5 - 7 6 - 8 7 - 9 8 - 10 9 Duan 11 10 - 12 11 Chang 13 12 Duan 14 13 Chang 15 14 - 16 15 - 17 16 Duan 18 17 Chang 19 17 - 20 19 - 21 20 - 22 21 - 23 22 - 24 23 - 25 24 - 26 25 Duan 27 26 - 28 27 Duan 29 28 - 30 29 Chang 31 28 - 32 31 Chang 33 32 - 34 32 - 35 34 - 36 ...
output:
YES 131 126 185 174 216 197 189 173 181 163 160 151 144 138 199 169 218 207 255 223 290 287 260 262 359 291 545 489 372 362 468 320 315 306 279 286 247 244 660 603 809 758 902 784 762 708 775 751 779 746 786 663 763 756 716 658 675 589 686 648 591 566 613 582 655 621 711 643 562 579 628 560 690 577 ...
result:
ok Correct.
Test #8:
score: 0
Accepted
time: 24ms
memory: 11196kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 5 Duan 7 6 - 8 7 - 9 8 - 10 9 Chang 11 10 - 12 11 Duan 13 12 Chang 14 13 - 15 14 Duan 16 15 Chang 17 16 - 18 17 - 19 18 Duan 20 19 - 21 20 - 22 21 - 23 22 Chang 24 23 - 25 24 Duan 26 25 - 27 26 Chang 28 27 - 29 28 - 30 29 - 31 30 Duan 32 31 - 33 32 - 34 33 - 35 34 - ...
output:
YES 161 155 251 249 292 277 424 430 381 368 353 383 386 380 422 429 493 490 532 528 545 526 551 534 540 531 556 555 665 661 642 641 650 639 646 638 624 622 625 621 614 612 630 627 618 615 609 598 706 700 725 718 820 786 875 873 852 835 909 903 865 857 866 850 813 802 810 801 772 770 698 696 780 694 ...
result:
ok Correct.
Test #9:
score: 0
Accepted
time: 25ms
memory: 15248kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 5 Duan 7 6 - 8 7 - 9 8 Chang 10 9 - 11 10 Duan 12 11 - 13 12 Chang 14 13 Duan 15 14 - 16 15 Chang 17 16 - 18 17 Duan 19 18 - 20 19 Chang 21 20 Duan 22 21 Chang 23 22 - 24 23 Duan 25 24 Chang 26 25 Duan 27 26 - 28 27 - 29 28 Chang 30 29 Duan 31 30 Chang 32 31 - 33 32 ...
output:
YES 308 306 357 356 453 450 556 554 552 549 548 547 570 568 569 567 682 676 672 671 737 738 735 728 805 801 806 794 793 791 910 908 922 914 952 946 1004 991 1016 1011 1024 1014 1164 1156 1160 1153 1155 1151 1147 1140 1102 1097 1094 1095 1093 1089 1076 1075 1123 1122 1129 1125 1135 1134 1154 1157 114...
result:
ok Correct.
Test #10:
score: 0
Accepted
time: 15ms
memory: 13640kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 5 - 7 6 - 8 7 - 9 8 - 10 9 - 11 10 - 12 11 - 13 12 - 14 13 - 15 14 - 16 15 - 17 16 - 18 17 - 19 18 - 20 19 - 21 20 - 22 21 - 23 22 - 24 23 - 25 24 - 26 25 - 27 26 - 28 27 - 29 28 - 30 29 - 31 30 - 32 31 - 33 32 - 34 33 - 35 34 - 36 35 - 37 36 - 38 37 - 39 38 - 40 39 ...
output:
YES 4774 4758 12004 11802 12878 12701 14403 14425 15175 15095 16272 16218 15813 15803 16111 15960 17703 17698 18828 18616 20553 20479 22767 22709 25371 24981 24571 23807 23781 23319 28616 28570 27425 26536 29756 29047 30157 29822 29413 29383 35528 35551 34909 34775 34774 33210 33101 33062 39883 3924...
result:
ok Correct.
Test #11:
score: 0
Accepted
time: 16ms
memory: 10700kb
input:
100000 2 1 - 3 1 - 4 2 - 5 1 - 6 1 - 7 2 Duan 8 4 - 9 1 - 10 1 - 11 2 - 12 2 - 13 2 - 14 6 - 15 1 - 16 6 - 17 1 - 18 5 - 19 1 - 20 1 - 21 2 - 22 8 - 23 6 - 24 1 - 25 4 Duan 26 1 - 27 10 - 28 1 - 29 8 - 30 5 - 31 7 - 32 2 - 33 3 - 34 12 - 35 3 - 36 1 - 37 12 - 38 8 - 39 8 - 40 1 - 41 4 - 42 16 - 43 8...
output:
YES 68260 71252 72829 93199 59385 11262 56366 7114 21981 56413 85882 70420 69070 88219 46636 70961 24045 70919 53558 8534 51312 6776 14730 47483 66745 8121 14466 42970 66071 3305 86329 37873 85723 12867 31531 39119 56430 82602 87213 34098 40456 67836 99956 24828 17961 87387 68937 87569 73357 91017 1...
result:
ok Correct.
Test #12:
score: 0
Accepted
time: 12ms
memory: 12644kb
input:
100000 2 1 - 3 1 - 4 1 - 5 1 - 6 1 - 7 1 - 8 1 - 9 1 - 10 3 - 11 1 - 12 2 - 13 2 - 14 2 - 15 1 - 16 2 - 17 2 - 18 1 - 19 1 - 20 1 - 21 2 - 22 1 - 23 2 - 24 2 - 25 1 - 26 1 - 27 4 - 28 1 - 29 2 - 30 3 - 31 1 - 32 10 - 33 6 - 34 4 - 35 1 - 36 2 Duan 37 1 - 38 4 - 39 10 - 40 1 - 41 1 - 42 3 - 43 6 - 44...
output:
YES 67589 89903 25532 2731 39272 68594 15090 81476 60781 71809 45615 98218 9592 13863 38360 41771 32307 67278 46144 98634 70045 36895 90229 56597 21515 87249 7445 44881 99328 70645 70229 51367 44757 15488 38942 68314 31755 361 53849 62803 74966 72268 38644 42791 39590 69049 31128 60607 68719 24390 2...
result:
ok Correct.
Test #13:
score: 0
Accepted
time: 22ms
memory: 11140kb
input:
100000 2 1 Duan 3 1 Duan 4 1 Duan 5 1 Duan 6 1 Duan 7 1 - 8 1 Duan 9 1 Duan 10 1 - 11 1 Duan 12 1 - 13 1 Duan 14 1 Duan 15 1 Duan 16 1 Duan 17 1 Duan 18 2 - 19 1 Duan 20 1 Duan 21 2 - 22 2 Duan 23 1 Duan 24 1 Duan 25 1 Duan 26 1 Duan 27 2 Duan 28 1 Duan 29 2 Duan 30 1 Duan 31 2 Duan 32 1 - 33 1 Duan...
output:
YES 97979 14629 58177 8043 77249 8022 99568 7886 97191 7106 79782 6452 98265 6438 52710 73953 38610 6320 84889 5888 81286 5812 41217 65693 97669 5668 65081 5312 71711 74586 77289 92388 89733 5206 73926 4798 99789 4777 38566 72776 79617 84855 67208 4736 91965 96692 58017 4470 82143 93682 98993 99395 ...
result:
ok Correct.
Test #14:
score: 0
Accepted
time: 13ms
memory: 12712kb
input:
100000 2 1 - 3 1 - 4 1 - 5 1 - 6 1 - 7 1 - 8 1 - 9 1 - 10 1 - 11 1 - 12 1 - 13 1 Duan 14 1 - 15 1 - 16 1 - 17 1 - 18 1 - 19 1 - 20 1 - 21 1 - 22 1 - 23 1 - 24 1 - 25 1 - 26 1 - 27 1 - 28 1 - 29 1 Duan 30 1 - 31 1 - 32 2 Duan 33 1 - 34 1 - 35 1 Duan 36 1 - 37 1 - 38 1 - 39 1 - 40 1 - 41 1 - 42 1 - 43...
output:
YES 85599 3382 95392 3013 79392 81526 76883 90600 47562 2266 67095 92236 82645 2087 83119 83294 86680 94655 53700 98104 59880 1891 84824 94429 38939 1867 72196 86276 74866 1851 73841 1832 33013 52187 75982 82555 60149 84502 77895 89910 90018 94488 52964 1798 62543 1780 45755 50707 63884 96747 67922 ...
result:
ok Correct.
Test #15:
score: 0
Accepted
time: 12ms
memory: 10612kb
input:
100000 2 1 Duan 3 1 - 4 1 - 5 1 Duan 6 1 - 7 1 - 8 1 - 9 1 - 10 1 - 11 1 - 12 1 - 13 1 - 14 1 - 15 1 - 16 1 - 17 1 - 18 1 - 19 1 - 20 1 - 21 1 - 22 1 - 23 1 - 24 1 - 25 1 - 26 1 - 27 1 - 28 1 - 29 1 - 30 1 - 31 1 - 32 1 - 33 1 Duan 34 1 - 35 1 - 36 1 - 37 1 - 38 1 - 39 1 - 40 1 - 41 1 - 42 1 - 43 1 ...
output:
YES 93600 1484 65492 1226 54647 80577 87425 98136 92548 1057 90647 95875 88522 91502 65449 864 63757 78454 57780 863 79380 91133 90975 859 77801 81087 69230 93397 63165 847 88299 841 61658 83594 91139 96200 67080 81529 96324 96779 74882 99215 99183 99293 56495 87893 78381 778 44807 81594 82056 767 8...
result:
ok Correct.
Test #16:
score: 0
Accepted
time: 21ms
memory: 12996kb
input:
100000 2 1 Duan 3 1 Duan 4 1 - 5 1 Duan 6 1 - 7 1 Duan 8 1 Duan 9 1 Duan 10 1 Duan 11 1 - 12 1 - 13 1 - 14 1 Duan 15 1 Duan 16 1 Duan 17 1 - 18 1 Duan 19 1 Duan 20 1 Duan 21 1 - 22 1 - 23 1 Duan 24 1 Duan 25 1 Duan 26 1 - 27 1 - 28 1 Duan 29 1 Duan 30 1 - 31 1 Duan 32 1 Duan 33 1 - 34 1 Duan 35 1 - ...
output:
YES 83464 705 95111 622 99954 575 91152 92518 93861 99688 92449 531 71582 528 66385 524 91774 518 95679 96388 95051 502 68161 495 92051 491 71560 79514 91617 486 92920 466 91709 456 69375 71375 82066 86414 94412 455 89074 451 86461 92101 97252 99900 86105 437 78526 436 65746 90094 82699 93000 84619 ...
result:
ok Correct.
Test #17:
score: 0
Accepted
time: 15ms
memory: 12608kb
input:
100000 2 1 - 3 1 - 4 2 - 5 2 - 6 2 Duan 7 3 - 8 1 - 9 1 - 10 6 - 11 3 - 12 2 - 13 7 - 14 1 - 15 9 - 16 11 - 17 13 - 18 9 - 19 16 - 20 19 - 21 8 - 22 5 - 23 14 - 24 21 - 25 21 - 26 16 - 27 5 - 28 5 - 29 19 - 30 8 - 31 24 - 32 30 - 33 12 Duan 34 9 - 35 12 Duan 36 6 - 37 15 - 38 26 - 39 29 - 40 13 - 41...
output:
NO
result:
ok Correct.
Test #18:
score: 0
Accepted
time: 12ms
memory: 12608kb
input:
100000 2 1 Duan 3 2 Duan 4 3 - 5 3 Duan 6 4 - 7 4 Duan 8 3 Duan 9 2 - 10 4 Duan 11 8 Duan 12 6 - 13 3 Duan 14 6 Duan 15 7 Duan 16 6 Duan 17 14 Tong 18 7 - 19 16 Duan 20 14 Duan 21 12 Duan 22 20 Duan 23 14 Duan 24 19 - 25 2 Duan 26 22 - 27 24 Duan 28 8 Duan 29 4 Duan 30 23 Duan 31 24 Duan 32 23 Duan ...
output:
NO
result:
ok Correct.
Test #19:
score: 0
Accepted
time: 17ms
memory: 12608kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 5 - 7 4 - 8 7 - 9 8 - 10 9 - 11 10 Duan 12 9 - 13 12 - 14 12 - 15 10 - 16 8 - 17 13 - 18 10 - 19 14 - 20 13 - 21 19 - 22 19 Duan 23 11 - 24 23 Duan 25 23 - 26 5 - 27 22 - 28 22 Duan 29 17 - 30 29 - 31 29 - 32 17 - 33 27 - 34 33 Duan 35 31 - 36 24 - 37 34 - 38 37 - 39...
output:
NO
result:
ok Correct.
Test #20:
score: 0
Accepted
time: 15ms
memory: 14652kb
input:
100000 2 1 Duan 3 2 Chang 4 3 - 5 4 - 6 5 - 7 6 Duan 8 7 - 9 8 Chang 10 9 Duan 11 10 Chang 12 11 - 13 12 Duan 14 13 Chang 15 13 - 16 15 - 17 15 - 18 15 Duan 19 18 - 20 19 Duan 21 19 Chang 22 20 - 23 22 - 24 21 Duan 25 23 - 26 22 - 27 25 Chang 28 26 - 29 28 Duan 30 24 Chang 31 28 - 32 23 - 33 28 - 34...
output:
NO
result:
ok Correct.
Test #21:
score: 0
Accepted
time: 18ms
memory: 12984kb
input:
100000 2 1 Duan 3 2 Chang 4 3 - 5 4 - 6 5 Duan 7 6 - 8 7 - 9 8 Chang 10 9 Duan 11 10 Chang 12 11 Duan 13 12 Chang 14 12 - 15 14 - 16 15 Duan 17 16 Chang 18 17 - 19 17 Duan 20 19 - 21 19 Chang 22 21 - 23 21 Duan 24 23 Duan 25 24 Chang 26 24 Chang 27 24 Duan 28 27 - 29 28 Chang 30 28 Duan 31 30 - 32 3...
output:
NO
result:
ok Correct.
Test #22:
score: 0
Accepted
time: 15ms
memory: 10856kb
input:
100000 2 1 Duan 3 2 Chang 4 3 Duan 5 4 - 6 5 Chang 7 6 - 8 7 Duan 9 8 - 10 9 Chang 11 10 Duan 12 11 Chang 13 12 - 14 13 Duan 15 14 - 16 15 Chang 17 16 - 18 17 Duan 19 18 - 20 19 - 21 20 - 22 21 Chang 23 22 - 24 23 Duan 25 24 Chang 26 25 - 27 26 Duan 28 27 - 29 28 Chang 30 28 Duan 31 30 - 32 31 Chang...
output:
NO
result:
ok Correct.
Test #23:
score: 0
Accepted
time: 10ms
memory: 13064kb
input:
100000 2 1 Duan 3 2 - 4 3 - 5 4 - 6 5 - 7 6 - 8 7 - 9 8 - 10 9 - 11 10 - 12 11 Chang 13 12 Duan 14 13 - 15 14 - 16 15 Chang 17 16 Duan 18 17 Chang 19 18 - 20 19 - 21 20 - 22 21 - 23 22 - 24 23 - 25 24 - 26 25 Duan 27 26 - 28 27 - 29 28 - 30 29 - 31 30 - 32 31 - 33 32 - 34 33 Chang 35 34 - 36 35 - 37...
output:
NO
result:
ok Correct.
Test #24:
score: 0
Accepted
time: 14ms
memory: 11404kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 5 Duan 7 6 - 8 7 Chang 9 8 - 10 9 - 11 10 - 12 11 - 13 12 - 14 13 Duan 15 14 - 16 15 Chang 17 16 - 18 17 - 19 18 - 20 19 Duan 21 20 - 22 21 - 23 22 - 24 23 Chang 25 24 - 26 25 Duan 27 26 Chang 28 27 Duan 29 28 - 30 29 - 31 30 - 32 31 Chang 33 32 Duan 34 33 - 35 34 - ...
output:
NO
result:
ok Correct.
Test #25:
score: 0
Accepted
time: 11ms
memory: 12632kb
input:
100000 2 1 Duan 3 1 - 4 1 - 5 1 - 6 3 - 7 2 - 8 2 - 9 4 - 10 1 - 11 2 - 12 3 Duan 13 2 - 14 4 - 15 3 - 16 3 - 17 2 - 18 2 - 19 1 - 20 7 Duan 21 1 - 22 15 - 23 6 - 24 1 - 25 8 - 26 11 - 27 5 - 28 16 - 29 17 - 30 16 - 31 3 - 32 7 - 33 3 Duan 34 7 Duan 35 3 - 36 8 - 37 6 - 38 16 - 39 3 - 40 3 - 41 11 -...
output:
NO
result:
ok Correct.
Test #26:
score: 0
Accepted
time: 14ms
memory: 12964kb
input:
100000 2 1 - 3 1 - 4 1 - 5 1 - 6 1 - 7 1 Duan 8 1 - 9 1 - 10 1 - 11 3 - 12 2 - 13 1 - 14 1 - 15 1 - 16 2 - 17 1 Duan 18 3 - 19 1 - 20 1 Duan 21 8 - 22 2 - 23 3 - 24 3 Duan 25 1 - 26 1 - 27 1 - 28 1 - 29 4 - 30 1 - 31 3 - 32 3 - 33 3 - 34 2 - 35 1 - 36 1 Duan 37 1 - 38 3 - 39 2 - 40 4 - 41 2 Duan 42 ...
output:
NO
result:
ok Correct.
Test #27:
score: 0
Accepted
time: 19ms
memory: 14824kb
input:
100000 2 1 Duan 3 1 Duan 4 1 Duan 5 1 Duan 6 1 Duan 7 1 Duan 8 1 Duan 9 1 Duan 10 1 Duan 11 1 Duan 12 1 Duan 13 1 Duan 14 2 Duan 15 1 Duan 16 1 Duan 17 1 Duan 18 2 Duan 19 1 Duan 20 1 - 21 1 Duan 22 1 Duan 23 1 Duan 24 1 Duan 25 1 Duan 26 1 Duan 27 2 Duan 28 1 Duan 29 1 Duan 30 1 - 31 1 Duan 32 1 Du...
output:
NO
result:
ok Correct.
Test #28:
score: 0
Accepted
time: 18ms
memory: 11040kb
input:
100000 2 1 - 3 1 Duan 4 1 - 5 1 - 6 1 - 7 1 Duan 8 1 - 9 1 Duan 10 1 - 11 1 Duan 12 1 Duan 13 1 Duan 14 1 Duan 15 1 Duan 16 1 - 17 1 Duan 18 1 Duan 19 1 Duan 20 1 Duan 21 1 - 22 1 - 23 1 Duan 24 1 - 25 1 Duan 26 1 Duan 27 1 Duan 28 1 Duan 29 1 Duan 30 1 Duan 31 1 Duan 32 1 - 33 1 - 34 1 Duan 35 1 Du...
output:
NO
result:
ok Correct.
Test #29:
score: 0
Accepted
time: 15ms
memory: 11124kb
input:
100000 2 1 Duan 3 1 Duan 4 1 Duan 5 1 Duan 6 1 Duan 7 1 Duan 8 1 - 9 1 Duan 10 1 Duan 11 1 Duan 12 1 - 13 1 Duan 14 1 Duan 15 1 Duan 16 1 Duan 17 1 Duan 18 1 Duan 19 1 Duan 20 1 - 21 1 - 22 1 Duan 23 1 - 24 1 Duan 25 1 Duan 26 1 Duan 27 1 Duan 28 1 Duan 29 1 Duan 30 1 Duan 31 1 Duan 32 1 Duan 33 1 -...
output:
NO
result:
ok Correct.
Test #30:
score: 0
Accepted
time: 23ms
memory: 13336kb
input:
100000 2 1 Duan 3 1 - 4 1 Duan 5 1 Duan 6 1 Duan 7 1 Duan 8 1 Duan 9 1 Duan 10 1 Duan 11 1 Duan 12 1 Duan 13 1 Duan 14 1 Duan 15 1 Duan 16 1 Duan 17 1 Duan 18 1 Duan 19 1 - 20 1 Duan 21 1 Duan 22 1 Duan 23 1 Duan 24 1 Duan 25 1 Duan 26 1 Duan 27 1 Duan 28 1 - 29 1 Duan 30 1 Duan 31 1 Duan 32 1 - 33 ...
output:
NO
result:
ok Correct.
Test #31:
score: 0
Accepted
time: 19ms
memory: 29724kb
input:
100000 2 1 Duan 3 2 - 4 3 Chang 5 4 - 6 5 Duan 7 6 Chang 8 7 - 9 8 - 10 9 Duan 11 10 Chang 12 11 Duan 13 12 Chang 14 13 Duan 15 14 Chang 16 15 - 17 16 - 18 17 - 19 18 Duan 20 19 - 21 20 - 22 21 Chang 23 22 Duan 24 23 Chang 25 24 - 26 25 Duan 27 26 Chang 28 27 Duan 29 28 - 30 29 Chang 31 30 Duan 32 3...
output:
YES 38669 38668 43574 43573 44576 44575 44897 44896 47955 47954 48087 48086 51732 51731 52699 52698 53053 53051 53844 53843 54080 54079 55170 55169 56248 56247 56591 56590 57029 57028 57090 57089 57209 57208 57206 57205 57692 57691 57809 57806 58262 58261 58319 58318 59077 59076 59131 59130 59428 59...
result:
ok Correct.
Test #32:
score: 0
Accepted
time: 10ms
memory: 12836kb
input:
100000 2 1 Duan 3 1 - 4 1 - 5 1 - 6 1 - 7 1 - 8 1 - 9 1 - 10 1 - 11 1 - 12 1 Tong 13 1 - 14 1 - 15 1 - 16 1 Tong 17 1 - 18 1 - 19 1 - 20 1 - 21 1 - 22 1 Tong 23 1 - 24 1 - 25 1 - 26 1 - 27 1 - 28 1 - 29 1 - 30 1 - 31 1 - 32 1 - 33 1 - 34 1 - 35 1 - 36 1 - 37 1 - 38 1 Tong 39 1 - 40 1 - 41 1 - 42 1 -...
output:
YES 90226 92627 80552 98157 66335 67953 85511 86134 86460 86996 89512 89806 92271 94233 96463 99736 48609 55714 56615 60624 64372 65770 69427 71357 72862 73888 73891 74512 77025 79593 80845 81710 81856 82075 82419 83893 85318 85374 85698 87691 88314 89327 89757 91747 92085 92584 93512 95440 97391 99...
result:
ok Correct.
Test #33:
score: 0
Accepted
time: 16ms
memory: 12724kb
input:
93284 2 1 - 3 1 Duan 4 2 - 5 4 - 6 2 - 7 4 Duan 8 1 - 9 4 - 10 4 Duan 11 6 - 12 7 - 13 6 - 14 1 Duan 15 4 - 16 9 - 17 12 - 18 15 - 19 6 Duan 20 1 - 21 15 - 22 2 - 23 5 Duan 24 7 - 25 22 - 26 13 - 27 12 - 28 6 - 29 27 Duan 30 7 Duan 31 9 - 32 14 - 33 3 - 34 21 - 35 18 - 36 35 - 37 7 - 38 17 Duan 39 2...
output:
YES 74513 20816 81879 66130 89777 35338 62475 73761 71335 37702 33453 23517 56223 15222 86688 91225 29499 7805 58463 86109 24560 41026 47941 5910 44357 15686 70706 20522 22815 9149 46379 66681 81135 71082 47858 24083 85674 46291 79873 75184 73465 87023 33095 41087 9719 56514 53207 3487 82993 58715 7...
result:
ok Correct.
Test #34:
score: 0
Accepted
time: 28ms
memory: 13168kb
input:
92284 2 1 Duan 3 2 - 4 3 Duan 5 2 Duan 6 3 - 7 4 Duan 8 6 Duan 9 4 Duan 10 6 Duan 11 4 Duan 12 8 Chang 13 1 Duan 14 5 Duan 15 5 - 16 15 Duan 17 15 Duan 18 13 Chang 19 12 Duan 20 4 - 21 1 Duan 22 17 Duan 23 2 Duan 24 14 Duan 25 17 Duan 26 22 Duan 27 4 - 28 26 Duan 29 9 Duan 30 15 Duan 31 3 Duan 32 7 ...
output:
YES 72399 59373 64277 59795 76031 62511 62495 48883 59778 39444 86492 16425 13682 49780 65245 46706 57764 46022 12089 12085 91021 12688 41203 66749 40403 17794 90300 62095 62751 58704 19440 22903 35611 40542 77274 71273 72403 27633 47603 27548 44456 44368 16807 41743 24344 12412 61518 41680 52077 61...
result:
ok Correct.
Test #35:
score: 0
Accepted
time: 25ms
memory: 12856kb
input:
93444 2 1 - 3 1 Duan 4 1 Duan 5 2 - 6 4 - 7 3 - 8 6 Duan 9 6 Duan 10 9 - 11 2 - 12 1 - 13 11 - 14 5 - 15 14 Duan 16 11 - 17 16 - 18 4 - 19 7 Duan 20 15 - 21 17 - 22 21 - 23 20 - 24 23 Duan 25 7 - 26 14 Duan 27 18 - 28 13 Duan 29 2 Duan 30 19 Duan 31 5 - 32 7 Duan 33 23 Duan 34 17 Duan 35 2 Duan 36 2...
output:
YES 36095 18291 42330 58464 65585 59400 28016 1955 74817 40901 53918 89642 4623 63353 84984 82334 61350 57215 68628 54608 89498 6183 51738 50593 59238 36029 76817 62682 78448 8962 53894 77371 25512 32196 36051 72379 61507 15907 45334 17172 24983 14874 57517 79759 7489 4252 58719 61241 40373 47115 20...
result:
ok Correct.
Test #36:
score: 0
Accepted
time: 26ms
memory: 13292kb
input:
98244 2 1 Duan 3 1 Duan 4 3 Duan 5 4 Duan 6 4 Duan 7 4 Duan 8 5 Duan 9 8 Duan 10 5 Duan 11 9 Duan 12 3 Duan 13 11 Tong 14 5 Duan 15 5 Duan 16 12 Duan 17 2 Duan 18 3 Duan 19 4 Duan 20 2 Duan 21 6 Duan 22 21 Duan 23 1 - 24 15 - 25 20 Duan 26 8 Duan 27 13 Duan 28 12 Duan 29 22 Duan 30 24 Duan 31 21 Dua...
output:
YES 38963 31567 95866 13251 95270 63302 92175 54023 59312 48934 93485 24639 26380 21809 59491 39929 74962 50304 93197 37132 32873 50798 89682 3734 10918 68142 77790 61493 13569 2062 44405 89860 13525 3203 69831 52369 49035 43739 38807 28930 75766 66372 39400 86527 15465 3875 26746 27472 26723 1690 1...
result:
ok Correct.
Test #37:
score: 0
Accepted
time: 4ms
memory: 10044kb
input:
25284 2 1 Duan 3 2 - 4 3 - 5 3 Duan 6 2 Duan 7 3 Duan 8 1 Duan 9 5 - 10 4 - 11 5 Duan 12 4 Duan 13 1 Duan 14 4 - 15 10 Duan 16 8 - 17 13 - 18 15 - 19 12 - 20 16 Duan 21 6 Duan 22 2 Duan 23 19 - 24 12 - 25 2 - 26 19 Duan 27 5 - 28 4 - 29 9 - 30 12 Duan 31 7 Duan 32 31 - 33 21 - 34 24 Duan 35 28 Duan ...
output:
YES 14626 21135 14096 13835 23638 4428 14105 14395 14359 8988 12572 18822 20771 1866 23534 15210 24821 7235 16843 1084 22081 18384 23584 9125 17968 7918 16796 24718 23519 8913 23223 3762 17039 1868 15456 7940 6852 2957 16581 14498 19923 9470 9699 1916 16119 17156 6193 1797 8613 13962 3543 18684 845 ...
result:
ok Correct.
Test #38:
score: 0
Accepted
time: 29ms
memory: 11056kb
input:
93246 2 1 Duan 3 2 Duan 4 3 Duan 5 1 - 6 4 Tong 7 4 Duan 8 4 Duan 9 8 - 10 6 Duan 11 2 Duan 12 1 Duan 13 11 Duan 14 8 Duan 15 1 Duan 16 8 Duan 17 10 Duan 18 3 Duan 19 1 Duan 20 18 Duan 21 10 Duan 22 14 Duan 23 11 Duan 24 19 Duan 25 21 Duan 26 17 Duan 27 24 Duan 28 24 Duan 29 17 Tong 30 23 Duan 31 17...
output:
YES 89030 81889 92091 44827 92357 18804 88411 71114 41235 19189 37071 26335 34183 92987 88624 13889 7117 5382 63386 9021 70522 26290 74182 44641 63647 36015 91664 90356 62270 48141 68439 32796 71774 29179 86091 76068 62275 27623 92998 19705 89771 11009 8510 4652 64403 3815 9990 40253 62617 1699 8489...
result:
ok Correct.
Test #39:
score: 0
Accepted
time: 24ms
memory: 13264kb
input:
99837 2 1 - 3 1 - 4 3 Duan 5 2 Duan 6 5 Duan 7 3 Duan 8 5 - 9 6 Duan 10 4 - 11 4 - 12 6 Duan 13 8 - 14 7 - 15 10 Duan 16 11 Duan 17 8 Duan 18 6 - 19 13 Duan 20 16 Duan 21 20 - 22 19 Chang 23 4 Duan 24 13 Duan 25 21 - 26 17 Duan 27 7 Duan 28 8 - 29 3 - 30 18 - 31 21 Duan 32 27 Duan 33 21 Duan 34 17 -...
output:
YES 92676 10410 64479 39274 94138 78859 30205 21274 30056 8785 37886 83693 88306 73635 28522 11691 57401 30919 64681 38138 9496 93491 63118 51332 66215 28452 92328 51297 94426 23727 77931 74562 34253 42129 48303 23327 51081 79346 74255 10299 78121 69759 64700 16245 84360 90972 62165 95214 17883 1087...
result:
ok Correct.
Test #40:
score: 0
Accepted
time: 26ms
memory: 13172kb
input:
91248 2 1 Duan 3 1 Duan 4 1 Duan 5 2 Duan 6 3 Duan 7 3 Chang 8 2 Duan 9 1 Duan 10 7 Duan 11 10 Duan 12 4 Duan 13 2 Duan 14 11 Duan 15 6 Duan 16 8 Duan 17 7 Duan 18 2 Duan 19 15 Duan 20 4 Duan 21 7 Duan 22 6 Duan 23 6 Duan 24 20 Duan 25 13 Duan 26 22 Duan 27 5 Duan 28 19 Duan 29 14 Duan 30 12 - 31 8 ...
output:
YES 88200 84342 84352 76377 63352 45791 88470 50883 44680 18535 31347 47797 50617 12022 66762 6719 67174 5130 89212 77457 66802 59725 69332 46630 90420 56151 48424 44293 74573 50828 46329 68733 19496 53256 32591 15888 80259 6154 25680 27747 81109 25066 32892 5287 10884 54094 89180 31562 2675 2581 87...
result:
ok Correct.
Test #41:
score: 0
Accepted
time: 25ms
memory: 12892kb
input:
93538 2 1 - 3 2 - 4 2 - 5 3 Duan 6 4 - 7 4 - 8 2 - 9 1 - 10 7 - 11 4 Duan 12 8 - 13 9 - 14 1 Duan 15 7 Duan 16 3 - 17 5 - 18 14 Duan 19 5 - 20 7 - 21 15 Duan 22 9 - 23 8 - 24 16 Duan 25 5 Duan 26 6 Duan 27 10 - 28 7 - 29 21 Duan 30 1 - 31 18 - 32 13 - 33 6 - 34 28 - 35 16 Duan 36 32 Duan 37 22 - 38 ...
output:
YES 71885 78212 37718 6100 49527 40991 92012 80389 81271 68659 54473 43095 79642 41814 57857 73661 48483 24540 52557 16398 41232 56423 62371 3709 48165 78939 74690 74318 68804 61871 24274 24101 70628 64890 84790 41770 53698 40451 39635 42520 91102 25034 90535 39256 77572 90078 91112 11894 72404 1639...
result:
ok Correct.
Test #42:
score: 0
Accepted
time: 26ms
memory: 12944kb
input:
92384 2 1 Duan 3 2 - 4 3 Duan 5 3 Duan 6 3 - 7 2 Duan 8 1 - 9 7 Duan 10 5 Chang 11 4 - 12 3 Duan 13 7 - 14 9 Duan 15 14 Chang 16 3 Duan 17 6 Duan 18 10 Duan 19 17 Duan 20 10 - 21 2 Duan 22 10 - 23 5 Duan 24 18 - 25 11 - 26 13 Duan 27 12 Duan 28 1 - 29 18 Duan 30 28 Duan 31 28 - 32 16 - 33 27 Duan 34...
output:
YES 65469 52483 66814 39644 44726 11062 79880 9868 59560 37247 88171 77144 76272 24217 61782 85792 80279 57105 68289 37735 58829 31363 44877 26773 91292 18959 57214 43740 15239 7777 90532 9911 7970 31792 48350 12673 70419 63278 78633 33091 87915 72507 71152 37461 55042 52979 72909 64528 44823 41920 ...
result:
ok Correct.
Test #43:
score: 0
Accepted
time: 0ms
memory: 5900kb
input:
1
output:
YES
result:
ok Correct.