QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#104901 | #6396. Puzzle: Kusabi | ckiseki# | WA | 34ms | 8308kb | C++20 | 3.8kb | 2023-05-12 13:35:37 | 2023-05-12 13:35:39 |
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 < S.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();
};
auto [tz, dz, z] = dfs(dfs, 0);
if (tz != '-') {
fail();
}
cout << "YES\n";
for (auto [x, y]: ans) {
cout << x + 1 << ' ' << y + 1 << '\n';
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3420kb
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: 2ms
memory: 3456kb
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: 0
Accepted
time: 2ms
memory: 3412kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 34ms
memory: 8308kb
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.