QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#378854 | #6396. Puzzle: Kusabi | BadMiiilk_# | WA | 27ms | 26012kb | C++23 | 3.5kb | 2024-04-06 14:58:37 | 2024-04-06 14:58:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ld long double
#define i64 __int128
#define PII pair<int,int>
#define endl '\n'
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
//cout<<setiosflags(ios::fixed)<<setprecision(K);
const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};
const double eps = 1e-9;
const double PI = acos(-1.0);
const int INF = 1e9 + 7;
const int mod = 998244353;
const int N = 2e5 + 10,M = N << 1;
void solve(){
int n;
cin >> n;
vector<vector<int>> g(n + 1);
vector<int> a(n + 1);
for(int i = 2;i <= n;i ++){
int x,y;
string op;
cin >> x >> y >> op;
g[x].push_back(y);
g[y].push_back(x);
if(op[0] == '-'){
a[i] = 0;
}else if(op[0] == 'T'){
a[i] = 1;
}else if(op[0] == 'D'){
a[i] = 2;
}else{
a[i] = 3;
}
}
vector<int> dep(n + 1);
// dep[1] = 1;
// vector<vector<vector<PII>>> cnt(n+1,vector<vector<PII>>(4));
bool ok = 1;
vector<PII> ans;
queue<PII> q;
vector<vector<priority_queue<PII>>> cnt(n+1,vector<priority_queue<PII>>(4));
function<void(int,int)> dfs = [&](int x,int fa){
if(ok == 0) return;
dep[x] = dep[fa] + 1;
for(auto item : g[x]){
if(item == fa) continue;
dfs(item,x);
for (int i = 1; i < 4; i++)
{
while (!cnt[item][i].empty())
{
cnt[x][i].push(cnt[item][i].top());
cnt[item][i].pop();
}
}
}
if (a[x]!=0){
cnt[x][a[x]].push({dep[x],x});
}
queue<PII> q;
while (cnt[x][1].size()>1)
{
auto [x1,idx1] = cnt[x][1].top();
cnt[x][1].pop();
auto [x2,idx2] = cnt[x][1].top();
if (x1!=x2){
// cnt[x][1].pop();
q.push({x1,idx1});
}else {
ans.push_back({idx1,idx2});
cnt[x][1].pop();
// cnt[x][].pop();
}
}
// if (q.size()+cnt[x][1].size()>1){
// ok =0 ;
// }
while (!q.empty())
{
cnt[x][1].push(q.front());
q.pop();
}
queue<PII> q2;
while (!cnt[x][2].empty()&&!cnt[x][3].empty())
{
auto [x1,idx1] = cnt[x][2].top();
auto [x2,idx2] = cnt[x][3].top();
if (x1>=x2){
q2.push({x1,idx1});
cnt[x][2].pop();
}else {
cnt[x][2].pop();
cnt[x][3].pop();
ans.push_back({idx1,idx2});
}
}
while (!q2.empty())
{
cnt[x][2].push(q2.front());
q2.pop();
}
if (cnt[x][1].size()+cnt[x][2].size()+cnt[x][3].size()>1){
ok =0;
}
};
dfs(1,0);
for(int i = 1;i <= 3;i ++){
if(cnt[1][i].size() != 0){
cout << "NO" << endl;
return;
}
}
if (ok){
cout << "YES\n";
for(auto [x,y]:ans){
cout << x<< ' '<< y<<'\n';
}
}else {
cout << "NO\n";
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
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: 3792kb
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: 3584kb
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 9 8 2 5 7 6
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 27ms
memory: 26012kb
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.