QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#103905 | #6396. Puzzle: Kusabi | jcccc | WA | 32ms | 7680kb | C++17 | 2.9kb | 2023-05-07 20:06:00 | 2023-05-07 20:06:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
const int N = 1e6 + 10;
const int M = 131;
const int INF = 0x3f3f3f3f;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
const long long mod = 1e9 + 7;
void solve(){
int n; cin >> n;
vector<int> val(n + 1);
vector<vector<int>> g(n + 1);
for(int i = 1; i < n; i++){
int a, b; cin >> a >> b;
g[b].push_back(a);
string s; cin >> s;
if(s == "-") continue;
if(s == "Tong") val[a] = 3;
else if(s == "Duan") val[a] = 1;
else val[a] = 2;
}
int flag = 1;
vector<PII> res;
vector<int> dep(n + 1);
function <void(int)> dfs1 = [&] (int u){
for(int v : g[u]){
dep[v] = dep[u] + 1;
dfs1(v);
}
};
function <int(int)> dfs2 = [&] (int u) -> int{
vector<int> aa, bb, cc;
for(int v : g[u]){
int num = dfs2(v);
if(!flag) return 0;
if(val[num] == 0) continue;
if(val[num] == 1) aa.push_back(num);
if(val[num] == 2) bb.push_back(num);
if(val[num] == 3) cc.push_back(num);
}
if(val[u] == 1) aa.push_back(u);
if(val[u] == 2) bb.push_back(u);
if(val[u] == 3) cc.push_back(u);
sort(aa.begin(), aa.end(), [&] (int a, int b){
return dep[a] < dep[b];
});
sort(bb.begin(), bb.end(), [&] (int a, int b){
return dep[a] < dep[b];
});
sort(cc.begin(), cc.end(), [&] (int a, int b){
return dep[a] < dep[b];
});
vector<int> num;
int k = 0, z = cc.size();
for(;k < z - 1; k += 2){
if(dep[cc[k]] == dep[cc[k + 1]]){
res.push_back({cc[k], cc[k + 1]});
continue;
}
num.push_back(cc[k]);
k--;
}
while(k < cc.size()) num.push_back(cc[k]), k++;
if(aa.size() > bb.size()){
int i = 0, j = 0;
for(; i < aa.size() && j < bb.size();){
if(dep[aa[i]] > dep[bb[j]]){
num.push_back(aa[i]);
i++;
}
else res.push_back({aa[i], bb[j]}), i++, j++;
}
while(i < aa.size()) num.push_back(aa[i]), i++;
while(j < bb.size()) num.push_back(bb[i]), j++;
}
else{
int i = 0, j = 0;
for(; i < aa.size() && j < bb.size();){
if(dep[aa[i]] > dep[bb[j]]){
num.push_back(aa[i]);
j++;
}
else res.push_back({aa[i], bb[j]}), i++, j++;
}
while(i < aa.size()) num.push_back(aa[i]), i++;
while(j < bb.size()) num.push_back(bb[i]), j++;
}
if(num.size() >= 2){
flag = 0;
return 0;
}
return (num.size() ? num[0] : 0);
};
dep[1] = 1;
dfs1(1);
int num = dfs2(1);
if(num != 0) flag = 0;
if(!flag) cout << "NO" << endl;
else{
cout << "YES" << endl;
for(auto [id1, id2] : res) cout << id1 << ' ' << id2 << endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(12);
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0 - 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3396kb
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: 2ms
memory: 3332kb
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 6 7 5
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3396kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 32ms
memory: 7680kb
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.