QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#470836 | #6396. Puzzle: Kusabi | lllei# | WA | 22ms | 8628kb | C++20 | 2.5kb | 2024-07-10 16:39:17 | 2024-07-10 16:39:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int type[maxn];
int n;
vector<int>G[maxn];
int dep[maxn];
vector<pair<int,int> >anss;
bool cmp(int x,int y)
{
return dep[x]<dep[y];
}
bool cmp2(pair<int,int> x,pair<int,int> y)
{
return dep[x.first]==dep[y.first]?x.second<y.second:dep[x.first]<dep[y.first];
}
vector<pair<int,int> >pos;
stack<int>t;
pair<int,int> dfs(int u)
{
vector<int>a[4];
//cout<<type[u]<<' '<<u<<endl;
if(type[u])a[type[u]].push_back(u);
for(auto v:G[u])
{
dep[v]=dep[u]+1;
pair<int,int> cur=dfs(v);
if(cur.first)a[cur.first].push_back(cur.second);
}
sort(a[1].begin(),a[1].end(),cmp);
pair<int,int>ans=make_pair(0,0);
for(int i=0;i<a[1].size();i++)
{
if(i+1<a[1].size()&&dep[a[1][i]]==dep[a[1][i+1]])anss.push_back(make_pair(a[1][i],a[1][i+1])),i++;
else
{
if(ans.first)
{
printf("NO\n");
exit(0);
}
else ans.first=type[a[1][i]],ans.second=a[1][i];
}
}
int cnt=0;
if(ans.first)cnt=1;
pos.clear();
for(int i=0;i<a[2].size();i++)pos.push_back(make_pair(a[2][i],2));
for(int i=0;i<a[3].size();i++)pos.push_back(make_pair(a[3][i],3));
sort(pos.begin(),pos.end(),cmp2);
for(auto s:pos)
{
if(s.second==3)
{
if(!t.empty())
{
anss.push_back(make_pair(s.first,t.top()));
t.pop();
}
else
{
ans.first=3;
ans.second=s.first;
cnt++;
}
}
else t.push(s.first);
}
while(!t.empty())
{
ans.first=2;
ans.second=t.top();
t.pop();
}
if(cnt>1)
{
printf("NO\n");
exit(0);
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=2;i<=n;i++)
{
int u,v;
char op[10];
scanf("%d%d%s",&u,&v,op);
G[v].push_back(u);
if(op[0]=='-')type[u]=0;
else if(op[0]=='T')type[u]=1;
else if(op[0]=='D')type[u]=2;
else type[u]=3;
}
pair<int,int>ans=dfs(1);
if(!ans.first)printf("YES\n");
else
{
printf("NO\n");
return 0;
}
//cout<<anss.size()<<endl;
for(auto p:anss)printf("%d %d\n",p.first,p.second);
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3784kb
input:
8 2 1 - 3 1 - 4 2 Tong 5 2 Tong 6 3 Duan 7 3 - 8 7 Chang
output:
YES 4 5 8 6
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 1ms
memory: 3808kb
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 10 3 8 9 6 2 5 7
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 22ms
memory: 8628kb
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 46666 56115 88119 38802 93143 10006 31531 76473 42604 15988 6569 30148 11412 2008 64525 46703 71289 70618 81204 47748 42353 46131 97634 20514 83516 82155 66867 62410 15712 9975 4978 3205 83026 5622 48783 10902 82167 30893 93809 65878 33377 66951 94549 66936 79128 64411 8453 22475 54702 36857 629...
result:
wrong answer Pair 42353-46131 symbol not satisfied.