QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#370982 | #6396. Puzzle: Kusabi | ricofx# | WA | 0ms | 11412kb | C++17 | 2.1kb | 2024-03-29 20:36:58 | 2024-03-29 20:36:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define enl putchar('\n')
const int MAXN = 1e5+5;
typedef pair<int,int> pii;
int n,m;
string s;
struct EG{
int to,nxt;
}e[MAXN];
int head[MAXN],etot;
inline void add(int u,int v){
e[etot]={v,head[u]};
head[u]=etot++;
}
vector<int>f[MAXN][3];
int fa[MAXN];
vector<pii>ans;
bool bfs(){
vector<int>vec;
queue<int>q;
q.push(1);
while(!q.empty()){
int u=q.front();q.pop();
vec.push_back(u);
for(int i=head[u];~i;i=e[i].nxt)
q.push(e[i].to);
}
reverse(vec.begin(),vec.end());
for(int u:vec){
// printf("%d %d %d\n",f[u][0].size(),f[u][1].size(),f[u][2].size());
if((f[u][1].size()>1)||(f[u][2].size()>1)||f[u][0].size() && (f[u][1].size() || f[u][2].size()))
return !printf("NO\n");
for(int i=0;i<3;++i)
if(!f[u][i].empty())
f[fa[u]][i].push_back(f[u][i][0]);
if(f[fa[u]][0].size()==2){
int x=f[fa[u]][0].back();f[fa[u]][0].pop_back();
int y=f[fa[u]][0].back();f[fa[u]][0].pop_back();
ans.push_back({x,y});
}
if(f[fa[u]][1].size() && f[fa[u]][2].size()){
ans.push_back({f[fa[u]][1].back(),f[fa[u]][2].back()});
f[fa[u]][1].pop_back();
f[fa[u]][2].pop_back();
}
}
if(f[1][0].size()||f[1][1].size()||f[1][2].size())
return !printf("NO\n");
return true;
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
memset(head,-1,sizeof(head));
cin>>n;
for(int i=1;i<n;++i){
int u,v;
cin>>u>>v>>s;
fa[v]=u;
add(v,u);
if(s=="Tong")f[u][0].push_back(u);
else if(s=="Duan")f[u][1].push_back(u);
else if(s=="Chang")f[u][2].push_back(u);
}
// for(int i=1;i<=n;++i,enl)
// for(int j=0;j<3;++j)
// // if(!f[i][j].empty())
// printf("%d ",f[i][j].size());
if(bfs()){
printf("YES\n");
for(auto [x,y]:ans)
printf("%d %d\n",x,y);
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 11156kb
input:
8 2 1 - 3 1 - 4 2 Tong 5 2 Tong 6 3 Duan 7 3 - 8 7 Chang
output:
YES 5 4 6 8
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 0ms
memory: 11412kb
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 9 8 3 10 2 6 7 5
result:
ok Correct.
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 11144kb
input:
2 2 1 Tong
output:
YES
result:
wrong answer Only odd number of marked vertices to match.