QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#131000 | #6396. Puzzle: Kusabi | segir187 | AC ✓ | 44ms | 33216kb | C++17 | 4.3kb | 2023-07-26 02:52:50 | 2023-07-26 02:52:53 |
Judging History
answer
#include <bits/stdc++.h> //Grzegorz Krawczyk
using namespace std;
typedef unsigned long long LL;
typedef long double LD;
#define rep(a,b) for(int a=0;a<int(b);a++)
#define rep2(a,b) for(int a=1;a<=(b);a++)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
const int INF=INT_MAX/2;
const LL LINF=LLONG_MAX/2;
const int LIM=1e5+7;
/// cd /mnt/c/Users/OEM/staszic-zadanka/wwi2023/taj/prog
///flagi kompilacji:
///g++ -std=c++17 -static -Wall -pedantic -O3 -s -lm -o taj taj.cpp
struct pomocy
{
int i;
int lvl;
char typ;
};
vector<int> G[LIM]; /// krawedzi wychodzace z danego wierzcholka
char type[LIM]; /// typ danego wierzcholka: = musi miec kolege tego samego poziomu, < wiekszego, > mniejszego
vector<pair<int,int>> ans; /// tu trzymam pary wierzcholkow juz sparowanych
pomocy dp[LIM]; /// trzymam kogo "przekazuje" do ojca
bool valid=1; /// czy istnieje odpowiedz
int n;
void debugv(vector<pair<int,int>>& v,string s)
{
cerr<<s<<": ";
for(auto [a,b]:v) cerr<<"{"<<a<<","<<b<<"} ";
cerr<<"\n";
}
void calcdp(int ja,int oj,int cnt)
{
if(!valid) return;
/// kazdy vector trzyma nr i glebokosc syna o danym znaku
vector<pair<int,int>> eq,les,mor;
for(auto a:G[ja]) /// wrzucam swoich synow do wektorow
{
if(a==oj) continue;
calcdp(a,ja,cnt+1);
if(dp[a].typ=='=') eq.pb({dp[a].lvl,dp[a].i});
else if(dp[a].typ=='<') les.pb({dp[a].lvl,dp[a].i});
else if(dp[a].typ=='>') mor.pb({dp[a].lvl,dp[a].i});
}
/// ----- wrzucam siebie do wlasciwego wektora, potem wszystkie sortuje po glebokosciach -----
if(type[ja]=='=') eq.pb({cnt,ja});
else if(type[ja]=='<') les.pb({cnt,ja});
else if(type[ja]=='>') mor.pb({cnt,ja});
sort(eq.begin(),eq.end());
sort(les.begin(),les.end());
sort(mor.begin(),mor.end());
/// ----- sprawdzam czy sumarycznie musze wypchnac >1 wierzcholek do ojca -----
if(int(eq.size()%2)+abs(int(les.size())-int(mor.size()))>1)
{
valid=0;
//cerr<<ja<<" w1\n";
//debugv(eq,"eq");
//debugv(les,"les");
//debugv(mor,"mor");
return;
}
/// ----- sprawdzam czy musze wypchnac jakis wierzcholek do ojca bedac korzeniem -----
if(ja==1&&(int(eq.size()%2)+abs(int(les.size())-int(mor.size()))>0))
{
valid=0;
//cerr<<ja<<" w2\n";
return;
}
/// ----- rozpatruje synow z = -----
for(int i=0;i<int(eq.size())-1;i+=2)
{
if(eq[i].st==eq[i+1].st)
{
ans.pb({eq[i].nd,eq[i+1].nd});
continue;
}
if((eq.size()%2==0)||(i%2==1))
{
valid=0;
//cerr<<ja<<" w3\n";
return;
}
dp[ja]={eq[i].nd,eq[i].st,'='};
i--;
}
if((eq.size()%2==1)&&dp[ja].i==0) dp[ja]={eq.back().nd,eq.back().st,'='};
/// ----- rozpatruje synow gdy wiecej < -----
if(les.size()>mor.size())
{
for(int i=(int)les.size()-1,j=(int)mor.size()-1;i>=0&&j>=0;i--,j--)
{
if(les[i].st<mor[j].st)
{
ans.pb({les[i].nd,mor[j].nd});
continue;
}
if(i==j)
{
valid=0;
//cerr<<ja<<" w4\n";
return;
}
dp[ja]={les[i].nd,les[i].st,'<'};
j++;
}
if(dp[ja].i==0) dp[ja]={les[0].nd,les[0].st,'<'};
return;
}
/// ----- rozpatruje synow gdy wiecej > lub po rowno <> -----
for(int i=0,j=0;i<int(les.size())&&j<int(mor.size());i++,j++)
{
if(les[i].st<mor[j].st)
{
ans.pb({les[i].nd,mor[j].nd});
continue;
}
if(les.size()==mor.size()||i!=j)
{
valid=0;
//cerr<<ja<<" w5\n";
return;
}
dp[ja]={mor[j].nd,mor[j].st,'>'};
i--;
}
if((les.size()<mor.size())&&dp[ja].i==0) dp[ja]={mor.back().nd,mor.back().st,'>'};
/* if(n==1e5&&ja==686)
{
cout<<ja<<": "<<type[ja]<<','<<ans.size()<<"\n";
cout<<eq.size()<<' '<<les.size()<<' '<<mor.size()<<'\n';
}
if(n==1e5&&dp[ja].i==68071)
{
cout<<ja<<":"<<ans.size()<<','<<oj<<" {"<<dp[ja].i<<','<<dp[ja].lvl<<','<<dp[ja].typ<<"} ";
cout<<eq.size()<<','<<les.size()<<','<<mor.size()<<'\n';
}*/
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n;
rep(i,n-1)
{
int a,b;
string s;
cin>>a>>b>>s;
G[a].pb(b);
G[b].pb(a);
if(s=="Tong") type[a]='=';
else if(s=="Duan") type[a]='<';
else if(s=="Chang") type[a]='>';
}
calcdp(1,1,1);
if(!valid)
{
cout<<"NO\n";
//for(auto [a,b]:ans) cerr<<a<<' '<<b<<'\n';
return 0;
}
cout<<"YES\n";
for(auto [a,b]:ans) cout<<a<<' '<<b<<'\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 6560kb
input:
8 2 1 - 3 1 - 4 2 Tong 5 2 Tong 6 3 Duan 7 3 - 8 7 Chang
output:
YES 4 5 6 8
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 2ms
memory: 7032kb
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 3 10 8 9 2 6 7 5
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 1ms
memory: 5804kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: 0
Accepted
time: 44ms
memory: 10736kb
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 46666 56115 38802 88119 10006 93143 76473 31531 15988 42604 6569 30148 2008 11412 46703 64525 70618 71289 47748 81204 20514 42353 46131 97634 82155 83516 62410 66867 9975 15712 3205 4978 5622 83026 10902 48783 30893 82167 65878 93809 33377 66951 66936 94549 64411 79128 8453 22475 36857 54702 629...
result:
ok Correct.
Test #5:
score: 0
Accepted
time: 23ms
memory: 10320kb
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 5203 28541 8106 5981 7551 7900 47998 53424 86909 91669 72002 40295 32334 65376 57528 95652 66693 91216 88445 98194 44959 54118 74202 76761 64661 71470 30271 85084 41192 60344 10342 41421 12876 79425 25933 35989 39297 41959 46303 94979 10581 46189 14956 51797 41806 82599 26090 60566 48923 94132 6...
result:
ok Correct.
Test #6:
score: 0
Accepted
time: 38ms
memory: 10524kb
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 19 20 55 65 52 53 46 48 35 36 22 34 58 61 56 57 1097 1206 1522 1593 1890 1938 1217 1365 1191 1295 2158 2188 1764 2845 1408 1646 3147 5721 2746 2810 2937 3194 2399 2710 3657 3778 2668 3580 2179 2259 2122 2174 2204 2379 2392 2449 2218 2499 2233 2369 2020 2077 8244 9174 14498 15184 14362 15193 1040...
result:
ok Correct.
Test #7:
score: 0
Accepted
time: 32ms
memory: 10448kb
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 81 85 105 107 103 117 168 172 273 275 321 333 369 384 314 327 433 463 429 437 543 588 667 639 1167 1273 1160 1375 1117 1176 995 1021 926 929 832 1059 1196 1242 1328 1329 1254 1259 1194 1213 1150 1275 1521 1689 1424 1620 1226 1229 1134 1277 915 1099 1218 1237 1316 1358 1284 1350 2462 2524 2128 23...
result:
ok Correct.
Test #8:
score: 0
Accepted
time: 34ms
memory: 10592kb
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 68 69 118 120 227 237 221 225 265 266 314 323 304 309 343 346 345 352 338 341 347 350 392 401 436 439 469 471 473 474 463 472 480 482 495 499 477 483 567 570 604 613 584 588 576 577 738 744 739 743 730 732 848 851 809 841 881 886 911 930 947 951 1007 1029 964 1002 946 958 914 919 939 942 952 959...
result:
ok Correct.
Test #9:
score: 0
Accepted
time: 39ms
memory: 10856kb
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 238 239 272 274 343 344 415 416 432 433 477 478 512 515 539 544 579 582 631 633 700 711 717 724 719 730 784 787 780 782 772 773 777 783 830 831 824 821 810 816 845 849 858 860 868 872 895 897 876 894 873 871 929 936 986 999 981 984 976 980 964 966 950 955 958 967 968 977 996 997 993 995 1038 103...
result:
ok Correct.
Test #10:
score: 0
Accepted
time: 20ms
memory: 11592kb
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 4915 4986 6570 6738 13597 14195 22019 22308 31792 31800 38225 38186 43803 43898 41995 41864 42327 42725 43807 43871 43542 43953 46356 46361 47608 47755 46932 47521 44955 46885 48486 48399 49839 50116 49668 49912 53355 54823 54273 54714 53853 54239 52524 52947 55640 57456 58053 58348 59228 59658 ...
result:
ok Correct.
Test #11:
score: 0
Accepted
time: 28ms
memory: 10664kb
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 34242 34406 14906 23870 28768 79207 50509 68052 32304 70759 36687 70523 36153 68751 3567 47669 18177 70173 50978 58218 56574 27598 6904 46683 47073 79895 4139 85751 17677 83196 65881 90916 44928 67031 25922 49996 28068 95211 43712 69374 19260 84697 32128 70765 30451 79850 12144 92289 51006 99611...
result:
ok Correct.
Test #12:
score: 0
Accepted
time: 28ms
memory: 10724kb
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 15102 66302 37177 40113 67735 67876 70745 98880 62593 71830 75547 84740 85699 88398 6455 71970 21755 84919 39981 74239 13515 71421 37672 71660 90862 91238 19470 42744 13573 72747 10218 81223 15063 87004 4280 19357 6427 44673 68085 92721 17731 33161 358 45357 49326 65914 45470 93622 15964 91832 3...
result:
ok Correct.
Test #13:
score: 0
Accepted
time: 24ms
memory: 10948kb
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 14063 27596 34955 38849 40110 41588 50491 54430 55203 61983 63894 69085 72241 72642 73765 75216 85544 88086 88697 95158 1136 15274 10786 18595 21493 24025 25178 30164 30800 40282 50699 52476 59910 76452 79238 86389 91441 96792 1197 30463 34098 46043 47433 49151 56601 57549 59254 65754 66989 8754...
result:
ok Correct.
Test #14:
score: 0
Accepted
time: 21ms
memory: 10876kb
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 51260 62964 64799 73003 87232 98672 31245 38059 47626 58383 78385 82570 84269 91105 67893 90700 95599 97507 51711 96567 2480 84425 90521 97467 3614 97387 2969 3281 3715 3958 3981 4406 4899 4989 5751 8199 8398 9076 9630 10568 11395 12991 13882 17448 17840 18138 18144 20327 24851 31941 34768 35502...
result:
ok Correct.
Test #15:
score: 0
Accepted
time: 27ms
memory: 10928kb
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 24271 32530 37384 38484 38738 38753 39458 39709 43803 46496 49018 49313 51853 53261 54125 54934 56321 59449 60751 62015 70717 81679 89831 97806 18859 26046 28373 30675 33247 34688 39921 43694 44356 46485 54712 55259 57280 57761 58304 58424 61007 61172 68370 71317 73029 73977 76662 88437 93135 97...
result:
ok Correct.
Test #16:
score: 0
Accepted
time: 25ms
memory: 10936kb
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 336 82705 60220 72014 80211 95022 93125 94029 59250 85950 77242 89854 56243 61755 80147 86382 86818 91748 408 37709 87876 89771 452 83493 481 97158 614 92488 824 95750 377 464 564 569 570 577 624 630 664 722 745 774 775 781 783 793 805 831 837 839 843 865 866 880 895 915 919 921 933 948 954 1007...
result:
ok Correct.
Test #17:
score: 0
Accepted
time: 22ms
memory: 10356kb
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: 32ms
memory: 10452kb
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: 25ms
memory: 10312kb
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: 27ms
memory: 10412kb
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: 29ms
memory: 10524kb
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: 19ms
memory: 9416kb
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: 26ms
memory: 9820kb
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: 30ms
memory: 11672kb
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: 18ms
memory: 10548kb
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: 22ms
memory: 10844kb
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: 25ms
memory: 10804kb
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: 14ms
memory: 10892kb
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: 28ms
memory: 11036kb
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: 24ms
memory: 11016kb
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: 36ms
memory: 33216kb
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 27101 27102 29449 29450 30581 30582 31108 31109 33544 33545 34348 34349 35394 35395 35626 35627 35741 35742 36325 36326 36979 36980 37025 37026 37780 37781 37916 37917 38565 38566 38778 38779 38882 38884 39162 39163 39440 39441 39609 39610 39688 39689 39923 39924 39994 39995 40980 40981 41017 41...
result:
ok Correct.
Test #32:
score: 0
Accepted
time: 17ms
memory: 10540kb
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 16519 19368 19370 20002 22372 23276 23623 23892 25053 25678 26012 26238 27219 27730 27745 28074 28638 28666 28834 29163 29193 29412 29427 29474 29584 29948 30011 30054 30281 30343 30739 30822 30976 30991 31022 31161 32140 32177 32415 32851 32863 32956 32972 33012 33083 33116 33338 33345 33410 33...
result:
ok Correct.
Test #33:
score: 0
Accepted
time: 37ms
memory: 10304kb
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 9427 44871 58881 75107 7193 33984 9737 33178 31043 89725 31602 50618 870 88133 52086 58845 21758 63567 16605 85296 28152 44633 2705 65095 18041 90927 42717 56227 10288 88253 16710 61450 49645 71661 30561 48970 20860 37354 31734 34821 29953 37862 37189 80450 56610 93257 14996 30431 42455 91146 34...
result:
ok Correct.
Test #34:
score: 0
Accepted
time: 29ms
memory: 10356kb
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 17459 51080 16873 32219 11101 56156 52633 74549 51694 82117 32559 38566 186 48460 25888 41891 83294 84667 52019 87183 77715 88982 13583 78351 83209 87627 46901 62069 8557 86376 986 3604 79770 83765 49864 80461 22996 74127 42259 69795 91303 61472 29187 35154 15829 25303 27245 62442 171 52319 3885...
result:
ok Correct.
Test #35:
score: 0
Accepted
time: 36ms
memory: 10240kb
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 54500 63791 4643 49024 37302 55459 26344 33770 28229 81449 65404 87768 24623 33539 51327 82147 90272 70787 9603 14888 47285 47877 29487 40135 353 4308 34651 72113 41429 58261 22648 64780 68254 81320 50381 57783 25357 85526 43913 76795 34185 41202 41133 46835 140 54622 10796 76020 1923 47575 1383...
result:
ok Correct.
Test #36:
score: 0
Accepted
time: 37ms
memory: 10564kb
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 16406 33409 15284 30277 6139 35906 58902 93724 18729 47922 20659 24670 41216 47533 48839 84590 4161 87728 74471 95897 3459 23810 9591 29076 9185 34342 80103 95194 22109 87229 14850 28966 8235 15423 13261 42356 9379 78438 35400 89672 33413 67130 9648 91476 23306 73800 877 79990 3540 87242 92296 9...
result:
ok Correct.
Test #37:
score: 0
Accepted
time: 11ms
memory: 7264kb
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 5340 14929 7415 15736 22917 23406 14380 15197 14590 24417 7880 3602 1894 15884 9136 12672 3206 5678 15621 24111 14368 20232 25101 21718 1931 7241 19471 24489 8812 23289 12521 22451 130 1629 21864 23008 3189 9095 15113 22734 10604 12465 6641 6996 1537 22852 765 23329 16208 20447 2439 18299 9351 1...
result:
ok Correct.
Test #38:
score: 0
Accepted
time: 31ms
memory: 10232kb
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 20027 82440 37790 82065 13555 55902 9444 93214 14967 54322 8102 47686 23936 71322 77717 78461 45254 48337 52000 83570 24317 29015 723 91719 35283 63413 3250 89556 60951 81387 50544 76768 6264 24023 27168 92751 65278 78391 14547 46265 81407 92070 47136 69857 17204 28099 19861 33721 24774 55462 33...
result:
ok Correct.
Test #39:
score: 0
Accepted
time: 30ms
memory: 10476kb
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 37610 77117 19111 30206 70345 88367 20744 36504 43637 75785 14266 79180 26231 83709 55639 85507 3564 10520 11286 21314 30850 90540 51043 56410 66938 77737 86756 89082 10348 37423 10238 81449 63757 89645 30451 42718 49790 91346 27842 74087 61765 86402 33536 73518 45163 55707 25335 33231 51349 766...
result:
ok Correct.
Test #40:
score: 0
Accepted
time: 35ms
memory: 10252kb
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 22567 91137 6625 32840 2746 72793 49857 58707 6406 9195 17873 75118 13271 70816 35070 36187 34727 36004 60624 77775 40146 56136 3419 7879 50744 81884 35818 75987 56940 90945 1090 12926 73408 77013 45541 48058 26944 55452 55908 58680 43609 78364 45709 77661 32151 55964 12836 71423 21580 52096 122...
result:
ok Correct.
Test #41:
score: 0
Accepted
time: 34ms
memory: 10240kb
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 19363 43838 42715 63190 10322 20329 78903 70798 14986 45972 62809 83054 1456 52182 19710 62218 84523 85461 12256 52940 7475 31914 39273 86366 21575 61296 12897 78432 23096 67416 61831 81263 686 53716 24734 31961 29776 45084 57302 70937 58268 25231 35275 85989 19412 19663 45326 70970 34007 55647 ...
result:
ok Correct.
Test #42:
score: 0
Accepted
time: 24ms
memory: 10192kb
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 40096 40387 43478 83783 3661 3917 50150 89303 15374 18917 34799 48940 61144 81225 63107 81589 20682 29948 1795 14730 13591 23638 2983 84669 33792 38473 26822 33668 72727 91365 52159 58495 10991 54079 69625 73581 31305 43086 39523 48339 14352 88518 65295 91546 34909 89085 3467 34637 17285 74155 9...
result:
ok Correct.
Test #43:
score: 0
Accepted
time: 2ms
memory: 5812kb
input:
1
output:
YES
result:
ok Correct.