QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#310374 | #6396. Puzzle: Kusabi | PlentyOfPenalty# | WA | 15ms | 11292kb | C++17 | 2.6kb | 2024-01-21 12:02:37 | 2024-01-21 12:02:37 |
Judging History
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());
pii pre(0,0);
//printf("Enter u=%d\n",u);
for(auto P:tong)
{
int d=P.first,u=P.second;
//printf("AddTong %d %d\n",d,u);
if(!pre.first)pre=P;
else if(pre.first==d)ans.emplace_back(pii(pre.second,u)), pre=pii(0,0);
else //pre.first!=d
{
if(!r[u])r[u]=pre.second,pre=P;
else fail();
}
}
if(pre.first)
{
if(!r[u])r[u]=pre.second;
else fail();
}
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 8272kb
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: 8272kb
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: 8316kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 15ms
memory: 11292kb
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.