QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#107148#6396. Puzzle: KusabikingsnowWA 30ms5272kbC++142.1kb2023-05-20 14:33:562023-05-20 14:33:57

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-20 14:33:57]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:5272kb
  • [2023-05-20 14:33:56]
  • 提交

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.