QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#252185 | #6396. Puzzle: Kusabi | ucup-team1074 | WA | 54ms | 15736kb | C++20 | 5.2kb | 2023-11-15 16:21:22 | 2023-11-15 16:21:22 |
Judging History
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 ; i >= 1 ;i --){
for(auto it : id[i]){
//对it点进行操作
vector<int>list[3];
for(int i = 0 ; i < 3 ; i ++)
list[i].clear();
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: 3ms
memory: 13188kb
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: 12900kb
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: 0ms
memory: 12908kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 54ms
memory: 15736kb
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.