QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104899 | #6396. Puzzle: Kusabi | ckiseki# | WA | 1ms | 3452kb | C++20 | 3.7kb | 2023-05-12 13:29:19 | 2023-05-12 13:29:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int cnt = sizeof...(T);
(..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
cerr << "\e[1;32m[ " << s << " ] = [ ";
for (int f = 0; L != R; ++L)
cerr << (f++ ? ", " : "") << *L;
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
void fail() {
cout << "NO\n";
exit(0);
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
vector<int> dep(n);
vector<int> p(n);
vector<char> type(n);
vector<vector<int>> g(n);
for (int i = 1; i < n; i++) {
int z;
string t;
cin >> z >> p[i] >> t;
--p[i];
dep[i] = dep[p[i]] + 1;
g[p[i]].push_back(i);
if (t == "Tong") {
type[i] = 'T';
} else if (t == "Chang") {
type[i] = 'L';
} else if (t == "Duan") {
type[i] = 'S';
} else {
type[i] = '-';
}
}
vector<pair<int,int>> ans;
const auto dfs = [&](auto self, int i) -> tuple<char,int,int> {
map<int,int> T;
vector<pair<int,int>> L, S;
const auto upd = [&T, &L, &S, &ans](char tt, int dd, int id) {
if (tt == 'T') {
if (auto it = T.find(dd); it != T.end()) {
ans.emplace_back(it->second, id);
T.erase(it);
} else {
T[dd] = id;
}
return;
}
if (tt == 'L') {
L.emplace_back(dd, id);
} else if (tt == 'S') {
S.emplace_back(dd, id);
}
};
upd(type[i], dep[i], i);
for (int j: g[i]) {
auto [tz, dz, z] = self(self, j);
upd(tz, dz, z);
}
if (abs(int(L.size()) - int(S.size())) + T.size() > 1) {
fail();
}
assert (T.size() <= 1 ||
L.size() == S.size() || L.size() == S.size() + 1
|| L.size() + 1 == S.size());
sort(L.begin(), L.end());
sort(S.begin(), S.end());
if (T.size() == 1 || L.size() == S.size()) {
for (size_t pos = 0; pos < L.size(); pos++) {
if (L[pos].first <= S[pos].first)
fail();
ans.emplace_back(L[pos].second, S[pos].second);
}
if (T.size() == 0)
return { '-', -1, -1 };
auto [dd, ii] = *T.begin();
return { 'T', dd, ii };
}
if (L.size() == S.size() + 1) {
for (size_t pos = 0; pos + 1 < L.size(); pos++) {
if (L[pos].first <= S[pos].first)
fail();
ans.emplace_back(L[pos].second, S[pos].second);
}
auto [dd, ii] = L.back();
return { 'L', dd, ii };
}
if (L.size() + 1 == S.size()) {
for (size_t pos = 1; pos < L.size(); pos++) {
if (L[pos - 1].first <= S[pos].first)
fail();
ans.emplace_back(L[pos - 1].second, S[pos].second);
}
auto [dd, ii] = S.front();
return { 'S', dd, ii };
}
__builtin_unreachable();
};
dfs(dfs, 0);
cout << "YES\n";
for (auto [x, y]: ans) {
cout << x + 1 << ' ' << y + 1 << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3452kb
input:
8 2 1 - 3 1 - 4 2 Tong 5 2 Tong 6 3 Duan 7 3 - 8 7 Chang
output:
YES 4 5 8 6
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 0ms
memory: 3424kb
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 10 3 8 9 6 2 5 7
result:
ok Correct.
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3392kb
input:
2 2 1 Tong
output:
YES
result:
wrong answer Only odd number of marked vertices to match.