QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#252140#6396. Puzzle: Kusabiucup-team1074WA 55ms15580kbC++205.2kb2023-11-15 15:55:512023-11-15 15:55:51

Judging History

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

  • [2023-11-15 15:55:51]
  • 评测
  • 测评结果:WA
  • 用时:55ms
  • 内存:15580kb
  • [2023-11-15 15:55:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
#define list sajioaw
const LL maxn = 4e05+7;
const LL N=1e05+10;
const LL mod=1e09+7;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >t;
priority_queue<LL> q;
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
int a[N];
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
struct Node{
	int fa;
	vector<int>ch;
	string str;
	int depth;
	int dai = 0;//携带的点
}tr[N];
//当一个点的所有儿子都被访问,那么该点将无法被访问
void dfs(){
	queue<Node>q;
	tr[1].depth = 1;
	tr[1].str = "-";
	q.push(tr[1]);
	while(!q.empty()){
		Node tmp = q.front();
		q.pop();
		for(auto it : tmp.ch){
			tr[it].depth = tmp.depth + 1;
			q.push(tr[it]);
		}
	}
}
int cmp(int a, int b){
	return tr[a].depth < tr[b].depth;
}
vector<int>id[N];
void solve() 
{
	cin >> n;
	for(int i = 2 ; i <= n ; i ++){
		int ch , fa;
		string s;
		cin >> ch >> fa >> s;
		tr[fa].ch.pb(ch);
		tr[ch].str = s;
		tr[ch].fa = fa;
	}
	dfs();
	int max_dep = 1;
	for(int i = 1 ; i <= n ; i ++){
		max_dep = max(max_dep , tr[i].depth); 
		id[tr[i].depth].pb(i);
	}
	vector< pair<int,int> >v;
	for(int i = max_dep - 1 ; i >= 1 ;i --){
		for(auto it : id[i]){
			//对it点进行操作
			vector<int>list[3];
			if(tr[it].str == "Tong"){
				list[0].pb(it);
			}
			if(tr[it].str == "Duan"){
				list[1].pb(it);			
			}
			if(tr[it].str == "Chang"){
				list[2].pb(it);				
			}
			for(auto x : tr[it].ch){
				if(tr[x].str == "Tong"){
					list[0].pb(x);
				}
				if(tr[tr[x].dai].str == "Tong"){
					list[0].pb(tr[x].dai);
				}
				if(tr[x].str == "Duan"){
					list[1].pb(x);
				}
				if(tr[tr[x].dai].str == "Duan"){
					list[1].pb(tr[x].dai);
				}
				if(tr[x].str == "Chang"){
					list[2].pb(x);
				}
				if(tr[tr[x].dai].str == "Chang"){
					list[2].pb(tr[x].dai);
				}
			}
			sort(list[0].begin() , list[0].begin() , cmp);
			sort(list[1].begin() , list[1].begin() , cmp);
			sort(list[2].begin() , list[2].begin() , cmp);
/*			printf("it : %d\n" , it);
			printf("list[0] : ");
			for(auto x :list[0]){
				cout<<x<<" ";
			}
			cout<<endl;
			printf("list[1] : ");
			for(auto x :list[1]){
				cout<<x<<" ";
			}
			cout<<endl;
			printf("list[2] : ");
			for(auto x :list[2]){
				cout<<x<<" ";
			}
			cout<<endl;*/
			int cnt = 0;
			int len = list[0].size();
			vector<int>res;//多于的下标
			if(len == 1){
				res.pb(list[0][0]);
			}
			for(int i = 1 ; i < len ; i ++){
				int x = list[0][i - 1] , y = list[0][i];
				if(tr[x].depth != tr[y].depth){
					res.pb(x);
					continue;
				}
				else{
					v.pb({x , y});
					i++;
				}
				if(i == len - 1){
					res.pb(list[0][len - 1]);
				}
			}
			int len1 = list[1].size() , len2 = list[2].size();
			//长保留长,短保留短
			if(len1 == len2){
				for(int i = 0 ; i < len1 ; i ++){
					int x = list[1][i] , y = list[2][i];
					if(tr[x].depth < tr[y].depth){
						v.pb({x , y});
					}			
					else{
						cout<<"NO\n";
						return;
					}
				}
			}
			else if(len1 - len2 == 1){
				if(res.size() == 1){
					cout<<"NO\n";
					return;			
				}
				else{//留短
					int f = 0;
					for(int i = len1 - 1; i >= 0 ; i --){
						if(!f){
							if(i == 0)
								break;
							int x = list[1][i] , y = list[2][i - 1];
							if(tr[x].depth < tr[y].depth){
								v.pb({x , y});
							}
							else{
								f = 1;
								res.pb(x);
								continue;
							}
						}
						else{
							int x = list[1][i] , y = list[2][i];
							if(tr[x].depth < tr[y].depth){
								v.pb({x , y});
							}			
							else{
								cout<<"NO\n";
								return;
							}
						}
					}
					if(!f){
						res.pb(list[1][0]);
					}
				}
			}
			else if(len2 - len1 == 1){
				if(res.size() == 1){
					cout<<"NO\n";
					return;			
				}
				else{//留长
					int f = 0;
					for(int i = 0 ; i < len1 ; i ++){
						if(!f){
							int x = list[1][i] , y = list[2][i];
							if(tr[x].depth < tr[y].depth){
								v.pb({x , y});
							}
							else{
								f = 1;
								i--;
								res.pb(y);
								continue;
							}
						}
						else{
							int x = list[1][i] , y = list[2][i + 1];
							if(tr[x].depth < tr[y].depth){
								v.pb({x , y});
							}			
							else{
								cout<<"NO\n";
								return;
							}
						}
					}
					if(!f){
						res.pb(list[2][len2 - 1]);
					}
				}				
			}
			else{
				cout<<"NO\n";
				return;					
			}
			if(res.size() > 1){
				cout<<"NO\n";
				return;
			}
			else if(res.size() == 1){
				if(res[0] != it){
					tr[it].dai = res[0];
					tr[it].str = "-";
				}
				if(i == 1){
					cout<<"NO\n";
					return;
				}
			}
			else{
				tr[it].str = "-";
			}
		//	cout<<tr[it].str<<endl;
		}
	}
	cout<<"YES\n";
	for(auto it : v){
		cout<<it.x<<" "<<it.y<<endl;
	}
}            
int main() 
{
    int t=1;
//	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 12752kb

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

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 5
7 6

result:

ok Correct.

Test #3:

score: 0
Accepted
time: 2ms
memory: 12840kb

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 55ms
memory: 15580kb

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.