QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#470651#6396. Puzzle: KusabiUESTC_xxx#WA 18ms15944kbC++201.6kb2024-07-10 15:40:562024-07-10 15:40:57

Judging History

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

  • [2024-07-10 15:40:57]
  • 评测
  • 测评结果:WA
  • 用时:18ms
  • 内存:15944kb
  • [2024-07-10 15:40:56]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
#define ll long long
#define lowbit(x) x&(-x)
using namespace std;
int n,s[500005],cy[500005],cx[500005],tot;
vector<int>e[500005];
struct node{
	int d,tp,id;
}p[500005],a[500005];
bool cmp(node a,node b){
	if(a.d==b.d) return a.tp<b.tp;
	return a.d<b.d;
}
void dfs(int u,int dp){
	p[u].id=u;
	p[u].d=dp;
	s[u]=(p[u].tp!=0);
	for(int i=0;i<e[u].size();++i){
		int v=e[u][i];
		dfs(v,dp+1);
		s[u]+=s[v];
	}
	int cnt=0;
	if(p[u].tp) cnt++,a[cnt]=p[u];
	for(int i=0;i<e[u].size();++i){
		int v=e[u][i];
		if(s[v]%2) cnt++,a[cnt]=p[v];
	}
	sort(a+1,a+cnt+1,cmp);
	int f=0;
	for(int i=1;i<=cnt;++i){
		if(a[i].tp==1){
			if(a[i+1].tp==1&&a[i+1].d==a[i].d&&i!=cnt){
				tot++,cx[tot]=a[i].id,cy[tot]=a[i+1].id;
				i++;
			}
			else f++,p[u]=a[i];
		}
	}
	queue<node>q;
	for(int i=1;i<=cnt;++i){
		if(a[i].tp==1) continue;
		if(a[i].tp==3){
			q.push(a[i]);
		}
		if(a[i].tp==2){
			if(!q.size()) f++,p[u]=a[i];
			else{
				node g=q.front();
				tot++,cx[tot]=g.id,cy[tot]=a[i].id;
				q.pop();
			}
		}
	}
	while(q.size()){
		f++,p[u]=q.front();
		q.pop();
	}
	if(f>1) printf("NO"),exit(0);
	if(u==1&&f) printf("NO"),exit(0);
}
int main(){
	scanf("%d",&n);
	for(int i=2;i<=n;++i){
		int x,y;
		char s[6];
		scanf("%d%d%s",&x,&y,s);
		e[y].push_back(x);
		if(s[0]=='T') p[x].tp=1;
		if(s[0]=='C') p[x].tp=2;
		if(s[0]=='D') p[x].tp=3;
	}
	dfs(1,0);
	printf("YES\n");
	for(int i=1;i<=tot;++i){
		printf("%d %d\n",cx[i],cy[i]);
	}
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 9928kb

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: 0ms
memory: 9924kb

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: 7836kb

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 18ms
memory: 15944kb

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:

NO

result:

wrong answer Jury has answer but participant has not.