QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#107148 | #6396. Puzzle: Kusabi | kingsnow | WA | 30ms | 5272kb | C++14 | 2.1kb | 2023-05-20 14:33:56 | 2023-05-20 14:33:57 |
Judging History
answer
//#pragma GCC optimize(3,"Ofast","inline")
//#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define getchar nc
#define sight(c) ('0'<=c&&c<='9')
#define swap(a,b) a^=b,b^=a,a^=b
#define LL long long
#define debug(a) cout<<#a<<" is "<<a<<"\n"
#define dput(a) puts("a")
#define eho(x) for(int i=head[x];i;i=net[i])
#define fi first
#define se second
inline char nc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
template <class T>
inline void read(T &x){// unsigned
static char c;
for (c=getchar();!sight(c);c=getchar());
for (x=0;sight(c);c=getchar())x=x*10+c-48;
}
template <class T> void write(T x){if (x<10) {putchar('0'+x); return;} write(x/10); putchar('0'+x%10);}
template <class T> inline void writeln(T x){ if (x<0) putchar('-'),x*=-1; write(x); putchar('\n'); }
template <class T> inline void writel(T x){ if (x<0) putchar('-'),x*=-1; write(x); putchar(' '); }
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define N 200007
int n,f[N],dep[N];
char ch[17];
vector<pii> ans,V,Vd,Vc;
signed main() {
#ifdef LOCAL
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
#endif
scanf("%d",&n);
for (int i=2;i<=n;i++) {
scanf("%d%d%s",&i,&f[i],ch);
dep[i]=dep[f[i]]+1;
if (ch[0]=='T') V.pb(pii(dep[i],i));
if (ch[0]=='D') Vd.pb(pii(dep[i],i));
if (ch[0]=='C') Vc.pb(pii(dep[i],i));
}
sort(V.begin(),V.end());
sort(Vd.begin(),Vd.end());
sort(Vc.begin(),Vc.end());
int last=-1;
for (auto Z:V) {
if (last==-1) last=Z.se;
else {
if (dep[last]!=Z.fi){
printf("NO");
exit(0);
} else {
ans.pb(pii(last,Z.se));
last=-1;
}
}
}
if (last!=-1) {
printf("NO");
exit(0);
}
if (Vd.size()!=Vc.size()) {
printf("NO");
exit(0);
}
for (int i=0;i<Vd.size();i++)
if (Vd[i].fi>=Vc[i].fi) {
printf("NO");
exit(0);
} else {
ans.pb(pii(Vd[i].se,Vc[i].se));
}
printf("YES\n");
for (auto Z:ans){
printf("%d %d\n",Z.fi,Z.se);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3584kb
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: 3552kb
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 2 6 7 5 3 10
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 30ms
memory: 5272kb
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 28763 61327 78961 79617 3156 3283 3681 7241 8241 8873 14132 15911 19874 24772 27446 28194 31315 33789 41090 52589 58699 59851 69010 69894 78400 79799 83333 85932 93895 95031 309 2042 2267 2564 3328 3940 5219 5411 6257 6310 7602 7965 8051 8063 10051 10294 10691 11158 13236 13533 14566 15047 15407...
result:
wrong answer Edge 59423-1 used twice.