QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#251987 | #6396. Puzzle: Kusabi | ucup-team1074 | WA | 27ms | 8548kb | C++20 | 2.2kb | 2023-11-15 14:06:10 | 2023-11-15 14:06:12 |
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;
}
}
vector<int>list[3];
vector<int>tr[N];
int depth[N];
void dfs(){
queue<int>q;
q.push(1);
depth[1] = 1;
while(!q.empty()){
int x = q.front();
q.pop();
for(auto it : tr[x]){
depth[it] = depth[x] + 1;
q.push(it);
}
}
}
int cmp(int a , int b){
return depth[a] < depth[b];
}
int cmp2(int a , int b){
return depth[a] > depth[b];
}
void solve()
{
cin >> n;
for(int i = 0 ;i < n ; i ++){
int ch , fa ;
string s;
cin >> ch >> fa >> s;
tr[fa].pb(ch);
if(s == "Tong"){
list[0].pb(ch);
}
else if(s == "Duan"){
list[1].pb(ch);
}
else if(s == "Chang"){
list[2].pb(ch);
}
}
dfs();
vector<pair<int , int > > v;
sort(list[0].begin() , list[0].end() , cmp);
if(list[0].size() % 2 == 1){
cout<<"NO\n";
return;
}
else{
for(int i = 0 ; i < list[0].size() ; i += 2){
int x = list[0][i] , y = list[0][i + 1];
if(depth[x] == depth[y]){
v.pb({x , y});
}
else{
cout<<"NO\n";
return;
}
}
}
sort(list[1].begin() , list[1].end() , cmp);
sort(list[2].begin() , list[2].end() , cmp);
if(list[1].size() != list[2].size()){
cout<<"NO\n";
return;
}
else{
for(int i = 0 ; i < list[1].size() ; i ++){
int x = list[1][i] , y = list[2][i];
if(depth[x] < depth[y]){
v.pb({x , y});
}
else{
cout<<"NO\n";
return;
}
}
}
cout<<"YES\n";
for(auto it : v){
cout<<it.x<<" "<<it.y<<endl;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout.precision(10);
int t=1;
// cin>>t;
while(t--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 6320kb
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: 5848kb
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 8 9 2 6 7 5 3 10
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 5952kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 27ms
memory: 8548kb
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 78961 61327 79617 28763 3283 78400 8241 93895 28194 69010 59851 85932 52589 27446 31315 7241 69894 83333 58699 33789 15911 19874 3681 24772 41090 95031 8873 3156 79799 14132 87751 74813 28273 85594 53651 61413 27407 11158 61255 27084 2042 86323 60707 54276 41654 35332 8051 63173 35912 79826 5203...
result:
wrong answer Edge 4707-66 used twice.