QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#236171 | #6396. Puzzle: Kusabi | Paxton# | AC ✓ | 85ms | 39544kb | C++23 | 5.9kb | 2023-11-03 17:32:27 | 2023-11-03 17:32:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
struct node
{
int sign, dep, id;
};
vector<int> edge[maxn];
int dep[maxn];
int sign[maxn];
vector<pair<int, int>> ans;
void dfs(int now, int fa)
{
dep[now] = dep[fa] + 1;
for (int i = 0; i < edge[now].size(); ++i)
{
int id = edge[now][i];
if (id == fa)
continue;
dfs(id, now);
}
}
node dfs1(int now, int fa)
{
vector<pair<int, int>> tmp[4]; // 待处理序列 tmp[sign] = {<dep,id>}
node retu = node{0, 0, 0}; // 当层返回值,id=-1表示无解,0表示没有点
for (auto a : edge[now])
{
if (a == fa)
continue;
node rec = dfs1(a, now); // return仅能返回一个点的值
if (rec.sign == -1) // 返回-1说明无解
return node{-1, -1, -1};
else if (rec.sign > 0) // 返回1,2,3说明有返回点
tmp[rec.sign].push_back({rec.dep, rec.id}); // 加入待处理序列
} // 所有儿子节点情况已经添加到tmp中
if (sign[now] != 0) // 自己拥有标记,加入匹配序列
tmp[sign[now]].push_back({dep[now], now});
for (int i = 1; i <= 3; ++i)
sort(tmp[i].begin(), tmp[i].end(), greater<pair<int, int>>()); // 按照dep降序排序
if (tmp[3].size())
{
int jishu = 1;
for (int i = 1; i < tmp[3].size(); ++i)
{
if (tmp[3][i].first != tmp[3][i - 1].first) // 存在tong无法匹配
{
if (jishu % 2) // 奇数个tong
{
if (retu.sign != 0) // 存在待返回值
return node{-1, -1, -1}; // 直接返回无解
retu = node{3, tmp[3][i - 1].first, tmp[3][i - 1].second}; // 否则加入返回值
}
for (int j = i - jishu; j < i - 1; j += 2)
ans.push_back({tmp[3][j].second, tmp[3][j + 1].second});
jishu = 1;
}
else
jishu++;
}
for (int i = tmp[3].size() - jishu; i < tmp[3].size() - 1; i += 2) // 处理最后一段tong
ans.push_back({tmp[3][i].second, tmp[3][i + 1].second});
if (jishu % 2) // 奇数个tong,最后一位多余
{
if (retu.sign != 0)
return node{-1, -1, -1};
retu = node{3, tmp[3][tmp[3].size() - 1].first, tmp[3][tmp[3].size() - 1].second};
}
}
if (tmp[1].size() == tmp[2].size()) // chang,duan长度相同
{
for (int i = 0; i < tmp[1].size(); i++)
{
if (tmp[1][i].first <= tmp[2][i].first)
return (node){-1, -1, -1};
ans.push_back({tmp[1][i].second, tmp[2][i].second});
}
}
else if (tmp[1].size() > tmp[2].size())
{
int zz = tmp[1].size() - 1; // zz表示chang的指针
for (int i = tmp[2].size() - 1; i >= 0; i--) // i表示duan的指针
{
while (zz >= 0 && tmp[1][zz].first <= tmp[2][i].first) // 若长指针深度小于短指针深度
{
if (retu.sign != 0)
return node{-1, -1, -1};
retu = node{1, tmp[1][zz].first, tmp[1][zz].second};
zz--;
}
if (zz >= 0 && tmp[1][zz].first > tmp[2][i].first) // 长指针深度大于短指针深度
{
ans.push_back({tmp[1][zz].second, tmp[2][i].second}); // 匹配
zz--; // 移位
}
else
return node{-1, -1, -1};
}
while (zz >= 0) // 如果duan匹配完了,但是chang还有剩余
{
if (retu.sign != 0)
return node{-1, -1, -1};
retu = node{1, tmp[1][zz].first, tmp[1][zz].second};
zz--; // 剩一个且之前没剩
}
}
else if (tmp[1].size() < tmp[2].size()) // 同理
{
int zz = 0;
for (int i = 0; i < tmp[1].size(); i++)
{
while (zz < tmp[2].size() && tmp[1][i].first <= tmp[2][zz].first)
{
if (retu.sign != 0)
return (node){-1, -1, -1};
retu = (node){2, tmp[2][zz].first, tmp[2][zz].second}, zz++;
}
if (zz < tmp[2].size() && tmp[1][i].first > tmp[2][zz].first)
{
ans.push_back({tmp[1][i].second, tmp[2][zz].second});
zz++;
}
else
return node{-1, -1, -1};
}
while (zz < tmp[2].size())
{
if (retu.sign != 0)
return node{-1, -1, -1};
retu = node{2, tmp[2][zz].first, tmp[2][zz].second};
zz++;
}
}
return retu;
}
int main()
{
int n;
cin >> n;
for (int i = 1; i < n; ++i)
{
int a, p, si = 0;
string t;
cin >> a >> p >> t;
if (t == "-")
si = 0;
else if (t == "Chang")
si = 1;
else if (t == "Duan")
si = 2;
else if (t == "Tong")
si = 3;
edge[p].push_back(a);
edge[a].push_back(p);
sign[a] = si;
}
dep[1] = 1;
dfs(1, 0);
node finish = dfs1(1, 0);
if (finish.sign == 0)
{
cout << "YES" << endl;
for (int i = 0; i < ans.size(); i++)
{
if (i != ans.size() - 1)
cout << ans[i].first << " " << ans[i].second << endl;
else
cout << ans[i].first << " " << ans[i].second;
}
}
else
cout << "NO";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 6336kb
input:
8 2 1 - 3 1 - 4 2 Tong 5 2 Tong 6 3 Duan 7 3 - 8 7 Chang
output:
YES 5 4 8 6
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 1ms
memory: 6160kb
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 10 3 9 8 6 2 5 7
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 5872kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: 0
Accepted
time: 75ms
memory: 10076kb
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 56115 46666 88119 38802 93143 10006 31531 76473 42604 15988 30148 6569 11412 2008 64525 46703 71289 70618 81204 47748 97634 46131 42353 20514 83516 82155 66867 62410 15712 9975 4978 3205 83026 5622 48783 10902 82167 30893 93809 65878 66951 33377 94549 66936 79128 64411 22475 8453 54702 36857 905...
result:
ok Correct.
Test #5:
score: 0
Accepted
time: 52ms
memory: 9952kb
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 28541 5203 5981 8106 7900 7551 53424 47998 91669 86909 40295 72002 65376 32334 95652 57528 91216 66693 98194 88445 54118 44959 76761 74202 71470 64661 85084 30271 60344 41192 41421 10342 79425 12876 35989 25933 41959 39297 94979 46303 46189 10581 51797 14956 82599 41806 60566 26090 94132 48923 7...
result:
ok Correct.
Test #6:
score: 0
Accepted
time: 85ms
memory: 10056kb
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 20 19 65 55 53 52 48 46 36 35 34 22 61 58 57 56 1206 1097 1593 1522 1938 1890 1365 1217 1295 1191 2188 2158 2845 1764 1646 1408 5721 3147 2810 2746 3194 2937 2710 2399 3778 3657 3580 2668 2259 2179 2174 2122 2379 2204 2449 2392 2499 2218 2369 2233 2077 2020 9174 8244 15184 14498 15193 14362 1069...
result:
ok Correct.
Test #7:
score: 0
Accepted
time: 60ms
memory: 10100kb
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 85 81 107 105 117 103 172 168 275 273 333 321 384 369 327 314 463 433 437 429 588 543 639 667 1273 1167 1375 1160 1176 1117 1021 995 929 926 1059 832 1242 1196 1329 1328 1259 1254 1213 1194 1275 1150 1689 1521 1620 1424 1229 1226 1277 1134 1099 915 1237 1218 1358 1316 1350 1284 2524 2462 2335 21...
result:
ok Correct.
Test #8:
score: 0
Accepted
time: 66ms
memory: 10272kb
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 69 68 120 118 237 227 225 221 266 265 323 314 309 304 346 343 352 345 341 338 350 347 401 392 439 436 471 469 474 473 472 463 482 480 499 495 483 477 570 567 613 604 588 584 577 576 744 738 743 739 732 730 851 848 841 809 886 881 930 911 951 947 1029 1007 1002 964 958 946 919 914 942 939 959 952...
result:
ok Correct.
Test #9:
score: 0
Accepted
time: 73ms
memory: 10928kb
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 239 238 274 272 344 343 416 415 433 432 478 477 515 512 544 539 582 579 633 631 711 700 724 717 730 719 787 784 782 780 773 772 783 777 831 830 821 824 816 810 849 845 860 858 872 868 897 895 894 876 871 873 936 929 999 986 984 981 980 976 966 964 955 950 967 958 977 968 997 996 995 993 1039 103...
result:
ok Correct.
Test #10:
score: 0
Accepted
time: 53ms
memory: 11624kb
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 4986 4915 6738 6570 14195 13597 22308 22019 31800 31792 38186 38225 43898 43803 41864 41995 42725 42327 43871 43807 43953 43542 46361 46356 47755 47608 47521 46932 46885 44955 48399 48486 50116 49839 49912 49668 54823 53355 54714 54273 54239 53853 52947 52524 57456 55640 58348 58053 59658 59228 ...
result:
ok Correct.
Test #11:
score: 0
Accepted
time: 41ms
memory: 10260kb
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 34406 34242 23870 14906 79207 28768 68052 50509 70523 36687 70759 32304 68751 36153 47669 3567 70173 18177 58218 50978 27598 56574 79895 47073 46683 6904 85751 4139 83196 17677 90916 65881 67031 44928 49996 25922 95211 28068 69374 43712 84697 19260 79850 70765 32128 30451 92289 12144 99611 51006...
result:
ok Correct.
Test #12:
score: 0
Accepted
time: 52ms
memory: 10300kb
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 75547 66302 84740 67876 67735 40113 98880 70745 88398 85699 71830 62593 37177 15102 71970 6455 84919 21755 74239 39981 71421 13515 91238 90862 71660 37672 42744 19470 72747 13573 90643 87004 81223 10218 92721 68085 44673 6427 19357 4280 33161 17731 45357 358 65914 49326 93622 45470 90190 35687 9...
result:
ok Correct.
Test #13:
score: 0
Accepted
time: 64ms
memory: 10520kb
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 95158 88697 88086 85544 75216 73765 72642 72241 69085 63894 61983 55203 54430 50491 41588 40110 38849 34955 27596 14063 15274 1136 96792 91441 86389 79238 76452 59910 52476 50699 40282 30800 30164 25178 24025 21493 18595 10786 30463 1197 96382 94062 87547 66989 65754 59254 57549 56601 49151 4743...
result:
ok Correct.
Test #14:
score: 0
Accepted
time: 47ms
memory: 10732kb
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 98672 87232 73003 64799 62964 51260 91105 84269 82570 78385 58383 47626 38059 31245 97507 95599 90700 67893 96567 51711 84425 2480 97467 90521 97387 3614 99880 90471 77306 65926 99206 90845 88745 84495 79862 68450 65516 63344 60150 53825 52602 52378 51834 47134 46820 41305 38081 37919 36133 3550...
result:
ok Correct.
Test #15:
score: 0
Accepted
time: 43ms
memory: 10716kb
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 97806 89831 81679 70717 62015 60751 59449 56321 54934 54125 53261 51853 49313 49018 46496 43803 39709 39458 38753 38738 38484 37384 32530 24271 99744 99690 97190 93135 88437 76662 73977 73029 71317 68370 61172 61007 58424 58304 57761 57280 55259 54712 46485 44356 43694 39921 34688 33247 30675 28...
result:
ok Correct.
Test #16:
score: 0
Accepted
time: 51ms
memory: 10428kb
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 82705 336 95022 80211 72014 60220 94029 93125 85950 59250 89854 77242 86382 80147 61755 56243 91748 86818 37709 408 89771 87876 83493 452 97158 481 92488 614 95750 824 99893 99214 98955 98785 98567 98351 98309 97651 97641 97468 97387 97134 97132 96795 96751 96749 96621 96201 96044 94858 94754 94...
result:
ok Correct.
Test #17:
score: 0
Accepted
time: 48ms
memory: 9888kb
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: 50ms
memory: 10240kb
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: 51ms
memory: 9864kb
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: 58ms
memory: 10228kb
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: 55ms
memory: 10296kb
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: 53ms
memory: 10044kb
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: 52ms
memory: 10552kb
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: 49ms
memory: 11720kb
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: 42ms
memory: 10160kb
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: 52ms
memory: 10352kb
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: 51ms
memory: 10448kb
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: 48ms
memory: 10528kb
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: 47ms
memory: 10636kb
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: 50ms
memory: 10648kb
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: 66ms
memory: 39544kb
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 27102 27101 29450 29449 30582 30581 31109 31108 33545 33544 34349 34348 35395 35394 35627 35626 35742 35741 36326 36325 36980 36979 37026 37025 37781 37780 37917 37916 38566 38565 38779 38778 38884 38882 39163 39162 39441 39440 39610 39609 39689 39688 39924 39923 39995 39994 40981 40980 41018 41...
result:
ok Correct.
Test #32:
score: 0
Accepted
time: 36ms
memory: 10088kb
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 99998 99975 99938 99920 99919 99897 99821 99793 99751 99703 99692 99689 99669 99634 99627 99620 99613 99530 99526 99507 99506 99464 99413 99351 99348 99308 99268 99250 99220 99200 99169 99137 99120 99102 99091 99077 99020 98994 98954 98914 98885 98847 98843 98822 98769 98742 98737 98709 98707 98...
result:
ok Correct.
Test #33:
score: 0
Accepted
time: 55ms
memory: 9736kb
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 44871 9427 75107 58881 33984 7193 33178 9737 89725 31043 50618 31602 88133 870 58845 52086 63567 21758 85296 16605 44633 28152 65095 2705 90927 18041 56227 42717 88253 10288 61450 16710 71661 49645 48970 30561 37354 20860 34821 31734 37862 29953 80450 37189 93257 56610 30431 14996 91146 42455 59...
result:
ok Correct.
Test #34:
score: 0
Accepted
time: 79ms
memory: 10016kb
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 51080 17459 32219 16873 56156 11101 74549 52633 82117 51694 38566 32559 48460 186 41891 25888 84667 83294 87183 52019 88982 77715 78351 13583 87627 83209 62069 46901 86376 8557 3604 986 83765 79770 80461 49864 74127 22996 69795 42259 61472 91303 35154 29187 62442 27245 25303 15829 71525 85158 84...
result:
ok Correct.
Test #35:
score: 0
Accepted
time: 60ms
memory: 9844kb
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 63791 54500 49024 4643 55459 37302 81449 28229 33770 26344 87768 65404 33539 24623 82147 51327 70787 90272 14888 9603 47877 47285 40135 29487 4308 353 72113 34651 58261 41429 64780 22648 81320 68254 57783 50381 85526 25357 76795 43913 41202 34185 46835 41133 76020 10796 54622 140 47575 1923 8801...
result:
ok Correct.
Test #36:
score: 0
Accepted
time: 83ms
memory: 10036kb
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 33409 16406 84590 30277 35906 6139 93724 58902 47922 18729 24670 20659 47533 41216 48839 15284 87728 4161 95897 74471 23810 3459 29076 9591 34342 9185 95194 80103 87229 22109 28966 14850 15423 8235 42356 13261 78438 9379 89672 35400 67130 33413 73800 23306 91476 9648 87242 3540 79990 877 94629 9...
result:
ok Correct.
Test #37:
score: 0
Accepted
time: 16ms
memory: 7016kb
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 14929 5340 15736 7415 23406 22917 15197 14380 24417 14590 3602 7880 15884 1894 12672 9136 5678 3206 24111 15621 20232 14368 21718 25101 7241 1931 24489 19471 23289 8812 22451 12521 1629 130 23008 21864 9095 3189 22734 15113 12465 10604 6996 6641 22852 1537 23329 765 20447 16208 18299 2439 13012 ...
result:
ok Correct.
Test #38:
score: 0
Accepted
time: 59ms
memory: 9884kb
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 82440 20027 82065 37790 55902 13555 54322 14967 93214 9444 47686 8102 71322 23936 78461 77717 48337 45254 83570 52000 29015 24317 91719 723 63413 35283 89556 3250 81387 60951 76768 50544 24023 6264 92751 27168 78391 65278 46265 14547 92070 81407 69857 47136 28099 17204 33721 19861 55462 24774 84...
result:
ok Correct.
Test #39:
score: 0
Accepted
time: 61ms
memory: 10076kb
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 77117 37610 30206 19111 88367 70345 36504 20744 75785 43637 79180 14266 83709 26231 85507 55639 21314 11286 10520 3564 90540 30850 56410 51043 77737 66938 89082 86756 37423 10348 81449 10238 89645 63757 42718 30451 91346 49790 74087 27842 86402 61765 73518 33536 55707 45163 33231 25335 76696 513...
result:
ok Correct.
Test #40:
score: 0
Accepted
time: 74ms
memory: 9808kb
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 91137 22567 32840 6625 72793 2746 58707 49857 9195 6406 75118 17873 70816 13271 36187 35070 36004 34727 77775 60624 56136 40146 7879 3419 81884 50744 75987 35818 90945 56940 12926 1090 77013 73408 48058 45541 55452 26944 58680 55908 78364 43609 77661 45709 55964 32151 71423 12836 52096 21580 629...
result:
ok Correct.
Test #41:
score: 0
Accepted
time: 52ms
memory: 9836kb
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 43838 19363 63190 42715 20329 10322 70798 78903 45972 14986 83054 62809 62218 19710 52182 1456 85461 84523 52940 12256 31914 7475 86366 39273 61296 21575 78432 12897 67416 23096 81263 61831 53716 686 31961 24734 45084 29776 70937 57302 25231 58268 85989 35275 19663 19412 70970 45326 55647 34007 ...
result:
ok Correct.
Test #42:
score: 0
Accepted
time: 67ms
memory: 9792kb
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 40387 40096 83783 43478 3917 3661 89303 50150 18917 15374 48940 34799 81225 61144 81589 63107 29948 20682 14730 1795 23638 13591 84669 2983 38473 33792 33668 26822 91365 72727 58495 52159 54079 10991 43086 31305 73581 69625 48339 39523 88518 14352 91546 65295 89085 34909 34637 3467 74155 17285 2...
result:
ok Correct.
Test #43:
score: 0
Accepted
time: 1ms
memory: 5900kb
input:
1
output:
YES
result:
ok Correct.