QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#228013 | #6394. Turn on the Light | kiwiHM# | TL | 0ms | 0kb | C++14 | 1.5kb | 2023-10-28 10:39:57 | 2023-10-28 10:39:57 |
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n;
int dep[maxn];
vector<pair<int, int> > ans;
vector<int> vec[3], tree[maxn];
inline void dfs(int u, int d){
dep[u] = d;
for(auto v: tree[u]) dfs(v, d + 1);
return;
}
int main(){
scanf("%d", &n);
for(int it = 1; it < n; ++it){
int i, p; scanf("%d%d", &i, &p); --i, --p;
char buf[15]; scanf("%s", buf);
tree[p].push_back(i);
if(buf[0] == 'D') vec[0].push_back(i);
else if(buf[0] == 'T') vec[1].push_back(i);
else if(buf[0] == 'C') vec[2].push_back(i);
}
dfs(0, 0);
for(int t = 0; t < 3; ++t) sort(vec[t].begin(), vec[t].end(), [&](const int &i, const int &j){ return dep[i] < dep[j]; });
if(vec[1].size() % 2 == 1){
puts("NO");
return 0;
}
for(int i = 0; i < vec[1].size(); i += 2){
if(dep[vec[1][i]] != dep[vec[1][i + 1]]){
puts("NO");
return 0;
}
ans.push_back(make_pair(vec[1][i], vec[1][i + 1]));
}
printf("shit %d %d\n", vec[0].size(), vec[2].size());
if(vec[0].size() != vec[2].size()){
puts("NO");
return 0;
}
for(int i = 0; i < vec[0].size(); ++i){
if(dep[vec[0][i]] >= dep[vec[2][i]]){
puts("NO");
return 0;
}
ans.push_back(make_pair(vec[0][i], vec[2][i]));
}
puts("YES");
for(auto p: ans) printf("%d %d\n", p.first + 1, p.second + 1);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3