QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#310389#6396. Puzzle: KusabiPlentyOfPenalty#WA 19ms11396kbC++172.5kb2024-01-21 12:08:482024-01-21 12:08:48

Judging History

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

  • [2024-01-21 12:08:48]
  • 评测
  • 测评结果:WA
  • 用时:19ms
  • 内存:11396kb
  • [2024-01-21 12:08:48]
  • 提交

answer

#include "bits/stdc++.h"
typedef long long ll;
using namespace std;
typedef std::pair<int,int> pii;
const int MAXN = 200011;
std::vector<int>g[MAXN];
std::vector<pii>tong,duan,chang,ans;
int type[MAXN],fa[MAXN],dep[MAXN];
int r[MAXN];
void fail()
{
	std::cout<<"NO"<<std::endl;
	exit(0);
}
void dfs(int u,int d)
{
	dep[u]=d;
	for(auto v:g[u])dfs(v,d+1);
	tong.clear(),duan.clear(),chang.clear();
	for(auto v:g[u])
		if(type[r[v]]==1)tong.emplace_back(pii(dep[r[v]],r[v]));
		else if(type[r[v]]==2)duan.emplace_back(pii(dep[r[v]],r[v]));
		else if(type[r[v]]==3)chang.emplace_back(pii(dep[r[v]],r[v]));
	if(type[u]==1)tong.emplace_back(pii(dep[u],u));
	else if(type[u]==2)duan.emplace_back(pii(dep[u],u));
	else if(type[u]==3)chang.emplace_back(pii(dep[u],u));
	sort(tong.begin(),tong.end());
	std::sort(duan.begin(),duan.end()),std::sort(chang.begin(),chang.end());
	//printf("Enter u=%d\n",u);
    r[u]=0;
	for(auto P:tong)
	{
		int d=P.first,x=P.second;
		//printf("AddTong %d %d\n",d,u);
		if(!r[u])r[u]=x;
        else if(dep[r[u]]!=d)fail();
        else
        {
            ans.emplace_back(pii(r[u],x));
            r[u]=0;
        }
	}
	
	int na=duan.size(),nb=chang.size(),flag=0;
	if(na>nb)flag=1;
	else flag=0;
	//printf("Na=%d,Nb=%d\n",na,nb);
	if(flag)
	{
		int it=nb-1;
		for(int i=na-1;i>=0;--i)
		{
			if(it>=0&&duan[i].first<chang[it].first)
			{
				ans.emplace_back(pii(duan[i].second,chang[it].second));
				--it;continue;
			}
			if(!r[u])r[u]=duan[i].second;
			else fail();
		}
        while(it>=0)
        {
            if(!r[u])r[u]=chang[it].second;
            else fail();
            --it;
        }
	}
	else
	{
		int it=0;
		for(int i=0;i<nb;++i)
		{
			if(it<na&&duan[it].first<chang[i].first)
			{
				ans.emplace_back(pii(duan[it].second,chang[i].second));
				++it;continue;
			}
			if(!r[u])r[u]=chang[i].second;
			else fail();
		}
        while(it<na)
        {
            if(!r[u])r[u]=duan[it].second;
            else fail();
            ++it;
        }
	}
	//printf("Quit %d,sz=%d\n",u,int(ans.size()));
}
int main()
{
#ifdef memset0
	freopen("C.in","r",stdin);
#endif
	cin.tie(0)->sync_with_stdio(0);
	int n;
	std::cin>>n;
	for(int i=2;i<=n;++i)
	{
		int u;
		string tp;
		cin>>u>>fa[u]>>tp;
		if(tp=="Tong")type[u]=1;
		else if(tp=="Duan")type[u]=2;
		else if(tp=="Chang")type[u]=3;
		g[fa[u]].emplace_back(u);
	}
	dfs(1,1);
	if(r[1])fail();
	cout<<"YES\n";
	for(auto P:ans)cout<<P.first<<" "<<P.second<<"\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 19ms
memory: 11396kb

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.