QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#380974 | #6396. Puzzle: Kusabi | invaded | AC ✓ | 43ms | 55636kb | C++17 | 3.8kb | 2024-04-07 15:43:59 | 2024-04-07 15:44:00 |
Judging History
answer
#include<bits/stdc++.h>
#ifndef xxx
#define dbg(...) ;
#endif
using namespace std;
template<class T> ostream &operator<<(ostream &o, const vector <T> &v) { bool f=false; for(T i:v) { f?o<<' ':o; o<<(i); f=true; } return o; }
template<class T> void sort(T &v) { std::sort(v.begin(), v.end()); }
template<class T, class C> void sort(T &v, C c) { std::sort(v.begin(), v.end(), c); }
template<class T> void reverse(T &v) { std::reverse(v.begin(), v.end()); }
template<class T> bool is_sorted(T &v) { return std::is_sorted(v.begin(), v.end()); }
template<class T> inline void left_shift(T st, T ed, int shift) { std::rotate(st, st+shift, ed); }
template<class T> inline void right_shift(T st, T ed, int shift) { std::rotate(st, ed-shift, ed); }
template<class T> inline void _min(T &x, const T &y) { x>y?x=y:x; }
template<class T> inline void _max(T &x, const T &y) { x<y?x=y:x; }
istream &operator>>(istream &i, __int128_t &x) { x=0; short f=1; char c=0; while(!isdigit(c)) { if(c=='-')f=-1; c=i.get(); } while(isdigit(c))x=x*10+c-'0', c=i.get(); x*=f; return i; }
ostream &operator<<(ostream &o, __int128_t x) { if(x==0) { o<<0; return o; } bool f=false; string s; if(x<0)f=true, x=-x; while(x)s+=x%10+'0', x/=10; reverse(s); if(f)o<<'-'; o<<s; return o; }
mt19937 mt(time(0));
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
constexpr int maxn=2e5+5;
constexpr int mod=1e9+7;
constexpr int inf=0x3f3f3f3f;
constexpr ll INF=0x3f3f3f3f3f3f3f3fll;
constexpr double pi=acos(-1.0);
constexpr double eps=1e-9;
struct node
{
int id, type, dep;
node() :id(0), type(0), dep(0) {}
node(int id, int type, int dep)
{
this->id=id;
this->type=type;
this->dep=dep;
}
}nd[maxn];
vector<int>G[maxn];
vector<int>layer[maxn];
// (dep,id)
set<pii>chang[maxn], duan[maxn], tong[maxn];
void dfs(int u)
{
//dbg(u);
layer[nd[u].dep].push_back(u);
for(int v:G[u])
{
dfs(v);
}
}
int main()//MARK: main
{
#ifndef xxx
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#endif
cout<<fixed<<setprecision(10);
int n;
cin>>n;
for(int i=1; i<=n-1; i++)
{
int id, type, dep;
int p;
string s;
cin>>id>>p>>s;
if(s[0]=='C')type=1;
else if(s[0]=='D')type=2;
else if(s[0]=='T')type=3;
else type=0;
dep=nd[p].dep+1;
nd[id]=node(id, type, dep);
G[p].push_back(id);
}
dfs(1);
vector<pii>ans;
auto getans=[&]()->bool
{
for(int d=n; d>=0; d--)
{
if(layer[d].empty())continue;
//dbg(d);
for(int u:layer[d])
{
auto [id, type, dep]=nd[u];
auto &C=chang[u];
auto &D=duan[u];
auto &T=tong[u];
for(int v:G[u])
{
C.insert(chang[v].begin(), chang[v].end());
D.insert(duan[v].begin(), duan[v].end());
T.insert(tong[v].begin(), tong[v].end());
}
if(type==1)C.insert({dep, u});
else if(type==2)D.insert({dep, u});
else if(type==3)T.insert({dep, u});
//dbg(u, type, C.size(), D.size(), T.size());
for(auto c=C.begin(); c!=C.end();)
{
auto it=D.lower_bound({c->first, 0});
if(it!=D.begin())
{
it--;
ans.push_back({c->second, it->second});
D.erase(it);
c=C.erase(c);
}
else
{
c++;
}
}
for(auto t=T.begin(); t!=T.end();)
{
auto nex=next(t);
if(nex!=T.end()&&nex->first==t->first)
{
ans.push_back({t->second, nex->second});
t=T.erase(t);
t=T.erase(t);
}
else
{
t++;
}
}
if(C.size()+D.size()+T.size()>1)
{
return false;
}
}
}
return chang[1].empty()&&duan[1].empty()&&tong[1].empty();
};
if(getans())
{
cout<<"YES"<<'\n';
for(auto [u, v]:ans)
{
cout<<u<<' '<<v<<'\n';
}
}
else
{
cout<<"NO"<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 43508kb
input:
8 2 1 - 3 1 - 4 2 Tong 5 2 Tong 6 3 Duan 7 3 - 8 7 Chang
output:
YES 4 5 8 6
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 3ms
memory: 43580kb
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 8 9 6 2 5 7
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 11ms
memory: 43740kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: 0
Accepted
time: 42ms
memory: 48332kb
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 77477 68238 92481 55487 90768 80321 61425 26757 85218 93032 79084 61332 81194 38376 96568 84503 87650 80329 90175 80462 91879 56280 80940 85183 92379 45401 51481 47304 48856 37299 68883 55343 86813 15089 65869 61306 55002 20320 69982 68591 74064 85031 73448 61051 45787 29361 42921 55495 95779 82...
result:
ok Correct.
Test #5:
score: 0
Accepted
time: 28ms
memory: 46884kb
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 85007 77529 91387 80143 85287 94990 89837 57819 74899 41068 70086 70043 37273 49983 76734 65251 87688 34335 46653 94573 86640 92239 88248 36497 82691 77530 61348 36957 87863 88167 85912 86273 32074 33907 71093 70825 57414 37315 90566 56018 98528 61875 85275 78637 83397 60916 86820 39881 99054 74...
result:
ok Correct.
Test #6:
score: 0
Accepted
time: 36ms
memory: 48912kb
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 97840 97601 99292 98570 99923 99872 98674 93657 99927 97278 97153 96917 91919 89534 90904 97037 93849 91562 99416 88445 93859 88743 98027 97734 95961 95886 99213 98352 98918 99109 98937 97464 87179 82392 98530 93746 93238 90982 97229 94748 98532 88190 97134 87701 92178 86074 96151 88169 86535 81...
result:
ok Correct.
Test #7:
score: 0
Accepted
time: 35ms
memory: 48136kb
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 92861 91954 93335 91434 93899 98059 97461 92444 95439 94537 94126 92799 89614 87516 97921 93526 92766 88597 98040 87784 94698 88134 96777 95134 99421 91610 87396 89001 86295 85711 89825 93157 97958 92889 90842 83443 84896 84005 91724 85808 95932 98810 99875 89502 87268 87098 91531 86158 96156 95...
result:
ok Correct.
Test #8:
score: 0
Accepted
time: 32ms
memory: 48452kb
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 99449 97710 98482 98203 99472 99169 99187 99881 99926 99695 99372 99486 96571 96519 94569 94328 99882 99179 99495 99924 94920 94118 97800 97267 98388 97034 98506 95628 99032 98256 99734 99105 98060 97831 95502 94210 98303 96199 99149 98563 99392 99312 99511 99191 98548 98119 98644 98661 98925 98...
result:
ok Correct.
Test #9:
score: 0
Accepted
time: 29ms
memory: 48816kb
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 99871 99002 99935 99455 98703 98568 99014 98775 99295 99051 98794 98330 98666 98596 98613 98728 98949 98537 98494 98269 99531 99308 99767 99464 99431 98981 97660 97740 97318 96790 99947 99570 97178 96958 99682 99555 99718 99413 99797 99690 98907 99288 99419 98180 98832 98556 99216 98632 99898 99...
result:
ok Correct.
Test #10:
score: 0
Accepted
time: 25ms
memory: 46772kb
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 99672 98805 98458 98016 98307 98030 97211 96964 99646 98406 99283 96353 97770 96874 95528 95149 95009 95727 95826 95032 93287 92731 93509 92589 94816 94115 92036 91889 99808 91071 98582 91183 93894 93463 95056 90894 88429 88023 93053 90013 91559 89615 91513 90450 88651 87571 88524 87267 89839 87...
result:
ok Correct.
Test #11:
score: 0
Accepted
time: 27ms
memory: 46028kb
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 80198 24098 88171 24783 40562 11139 73062 29042 99142 65243 78891 93050 79869 50504 36153 68751 63196 83117 79302 17788 60234 6386 46536 98139 48385 15034 57729 15842 61505 37679 35563 67516 29431 89988 78374 7572 46167 96843 37345 5629 20243 73598 55234 42327 60615 14379 94930 28006 58735 62595...
result:
ok Correct.
Test #12:
score: 0
Accepted
time: 28ms
memory: 45100kb
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 99253 24514 15102 66302 37177 40113 67735 67876 70745 98880 74239 39981 71421 13515 13573 72747 49326 65914 66307 5659 74307 6751 68801 93527 25142 65868 49908 92842 92302 28268 10387 4763 77194 4231 41886 2882 23941 64953 65085 50595 25338 2766 35889 92736 50684 5973 39951 75236 45778 7638 6566...
result:
ok Correct.
Test #13:
score: 0
Accepted
time: 37ms
memory: 48116kb
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 15274 1136 14063 27596 34955 38849 40110 41588 50491 54430 55203 61983 63894 69085 72241 72642 73765 75216 85544 88086 88697 95158 30463 1197 10786 18595 21493 24025 25178 30164 30800 40282 50699 52476 59910 76452 79238 86389 91441 96792 35120 1212 34098 46043 47433 49151 56601 57549 59254 65754...
result:
ok Correct.
Test #14:
score: 0
Accepted
time: 15ms
memory: 45404kb
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 84425 2480 90521 97467 97387 3614 67504 76866 48982 97376 61972 73151 90926 95255 63972 2988 65309 3348 66342 88130 40816 71350 67502 2595 99364 5612 96840 7802 92365 95951 890...
result:
ok Correct.
Test #15:
score: 0
Accepted
time: 24ms
memory: 44832kb
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: 27ms
memory: 46536kb
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 60220 72014 80211 95022 93125 94029 59250 85950 77242 89854 56243 61755 80147 86382 37709 408 86818 91748 87876 89771 83493 452 97158 481 92488 614 95750 824 78516 409 96448 598 86064 2 76526 86859 77425 78815 82710 60638 89238 34692 93523 11713 95747 4966 97446 4358 97896 4090 98648 3...
result:
ok Correct.
Test #17:
score: 0
Accepted
time: 30ms
memory: 45880kb
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: 26ms
memory: 46744kb
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: 15ms
memory: 45960kb
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: 47548kb
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: 32ms
memory: 47620kb
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: 39ms
memory: 48172kb
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: 31ms
memory: 46712kb
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: 12ms
memory: 46624kb
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: 19ms
memory: 44916kb
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: 21ms
memory: 45908kb
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: 29ms
memory: 48652kb
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: 27ms
memory: 46036kb
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: 33ms
memory: 48676kb
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: 31ms
memory: 49256kb
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: 34ms
memory: 55636kb
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 100000 99999 99994 99993 99992 99989 99988 99987 99986 99985 99983 99981 99976 99975 99974 99972 99970 99969 99971 99966 99965 99964 99967 99963 99962 99961 99959 99957 99960 99958 99956 99954 99945 99944 99952 99947 99949 99948 99942 99937 99939 99938 99933 99932 99936 99935 99931 99928 99930 9...
result:
ok Correct.
Test #32:
score: 0
Accepted
time: 19ms
memory: 45176kb
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 71956 2 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 ...
result:
ok Correct.
Test #33:
score: 0
Accepted
time: 39ms
memory: 47112kb
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 66636 39643 59669 73972 29538 39373 43825 45676 92094 61662 56374 54079 58779 51777 92038 89214 79715 51729 91931 52001 59992 54089 65054 26175 65249 59652 50472 46097 37619 28787 70144 48367 68486 73300 15616 71114 87207 39620 82288 63988 31389 11598 30372 27837 36554 49740 71700 33598 60608 76...
result:
ok Correct.
Test #34:
score: 0
Accepted
time: 37ms
memory: 48296kb
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 70030 17095 58313 71886 81302 88337 61987 46082 58426 49044 69693 53023 89381 83035 87654 75689 83186 69877 57838 76609 79463 38920 46779 36841 74808 37289 86286 50554 90294 83917 55098 21741 38474 26076 83059 58922 75451 75306 80380 72392 61439 58108 41745 32197 92181 44566 87864 8778 54941 658...
result:
ok Correct.
Test #35:
score: 0
Accepted
time: 37ms
memory: 47988kb
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 90448 71063 70985 47226 54731 53817 71130 60928 60775 52065 92806 53816 78644 61834 66621 34925 91538 76915 72307 61559 77871 61678 78776 56059 50496 61249 52856 62538 54218 50118 46399 88965 39731 56708 71777 57283 68919 25314 74435 43914 73589 40564 75837 70446 53440 29110 81837 64465 72630 92...
result:
ok Correct.
Test #36:
score: 0
Accepted
time: 43ms
memory: 48656kb
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 81930 66577 83933 77584 92455 63072 71866 67573 92912 72371 70317 63337 70245 61159 94399 52559 65297 80055 85114 72465 59449 43588 85452 75636 64850 58621 29443 31276 56643 48922 51157 23195 88704 28814 89798 62845 81017 90058 94855 86719 64539 42364 92183 56961 94394 37510 66889 51463 89546 86...
result:
ok Correct.
Test #37:
score: 0
Accepted
time: 11ms
memory: 44788kb
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 16618 15103 21994 23516 16434 8235 22264 9591 21246 12691 19880 8616 20031 19343 22971 21772 24144 21287 18950 13423 22868 22122 24765 13258 16589 9420 20892 14003 12386 4662 6480 7451 23940 18730 22041 16708 12213 11390 24705 20929 25137 18882 24686 15277 9392 12423 18580 16897 17297 16147 2467...
result:
ok Correct.
Test #38:
score: 0
Accepted
time: 43ms
memory: 48344kb
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 87399 47101 84050 60086 64188 39053 73100 60799 91714 27729 37196 51058 86184 57410 88324 31825 84986 92590 87646 24943 35872 23925 89760 78293 27833 22558 67687 48734 89379 75253 83797 61040 84043 74594 35199 32439 84021 35795 88437 71668 16888 84125 22901 12330 29387 25486 77362 61771 85450 70...
result:
ok Correct.
Test #39:
score: 0
Accepted
time: 34ms
memory: 48200kb
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 64748 50583 99612 83879 55350 47764 84477 44945 60215 65354 51316 51254 59804 54560 73704 64777 89280 79685 76854 82652 61141 34349 67573 62762 80616 30362 80150 51451 63900 34986 91487 88309 99160 78819 66253 55300 70840 50766 70421 26423 60649 32935 86183 60238 97034 86632 46625 43300 24793 30...
result:
ok Correct.
Test #40:
score: 0
Accepted
time: 35ms
memory: 48596kb
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 78204 78156 51967 36397 82427 78133 79070 73958 57455 38876 43404 34717 58713 48285 37948 36514 64018 88498 72670 68802 87893 81149 85556 22228 24511 53774 61304 43245 59479 58325 88072 79174 89317 76311 83169 60999 89571 71803 50155 34101 76502 34710 65296 44985 90010 21100 53737 28817 67079 31...
result:
ok Correct.
Test #41:
score: 0
Accepted
time: 37ms
memory: 47656kb
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 85877 84470 56796 84813 88602 42797 68533 60185 81856 70827 84668 60101 92180 86069 44601 43585 90933 90588 38530 51632 66807 64621 38876 40261 54401 71776 90432 70527 67445 35538 62691 83494 87364 64876 78467 42123 57243 51661 18333 81751 87803 76922 88298 51577 74165 66806 90940 82624 91473 63...
result:
ok Correct.
Test #42:
score: 0
Accepted
time: 34ms
memory: 47836kb
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 84069 61403 92293 84102 88097 64473 81431 55424 72143 51261 86058 79826 92072 52423 63157 47929 82708 67233 91160 89940 76454 57962 57177 51909 60350 59297 85916 62145 66794 35934 50820 36823 86852 55573 69228 68102 66952 44978 75739 39762 87714 86019 88236 32949 64172 49775 49389 33426 50738 52...
result:
ok Correct.
Test #43:
score: 0
Accepted
time: 3ms
memory: 43772kb
input:
1
output:
YES
result:
ok Correct.