QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#103924 | #6396. Puzzle: Kusabi | hos_lyric | WA | 20ms | 8868kb | C++14 | 3.7kb | 2023-05-07 20:54:44 | 2023-05-07 20:54:46 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
int N;
vector<int> P;
vector<char> T;
bool solve() {
vector<int> dep(N, 0);
for (int u = 1; u < N; ++u) {
dep[u] = dep[P[u]] + 1;
}
vector<vector<int>> dp(N);
for (int u = 0; u < N; ++u) if (T[u] != '-') {
dp[u].push_back(u);
}
vector<pair<int, int>> ans;
for (int u = N; --u >= 0; ) {
vector<pair<int, int>> cs, ds, ts;
for (const int v : dp[u]) {
((T[v] == 'C') ? cs : (T[v] == 'D') ? ds : ts).emplace_back(dep[v], v);
}
// cerr<<u<<": "<<cs<<" "<<ds<<" "<<ts<<endl;
sort(cs.begin(), cs.end());
sort(ds.begin(), ds.end());
sort(ts.begin(), ts.end());
const int csLen = cs.size();
const int dsLen = ds.size();
const int tsLen = ts.size();
vector<int> remain;
if (csLen <= dsLen) {
// keep smallest in ds
reverse(cs.begin(), cs.end());
reverse(ds.begin(), ds.end());
vector<int> used(dsLen, 0);
for (int i = 0, j = 0; i < csLen; ++i) {
for (; j < dsLen && !(cs[i].first > ds[j].first); ++j) {}
if (j == dsLen) return false;
used[j] = 1;
ans.emplace_back(cs[i].second, ds[j].second);
}
for (int j = 0; j < dsLen; ++j) if (!used[j]) {
remain.push_back(ds[j].second);
}
} else {
// keep largest in cs
vector<int> used(csLen, 0);
for (int i = 0, j = 0; j < dsLen; ++j) {
for (; i < csLen && !(cs[i].first > ds[j].first); ++i) {}
if (i == csLen) return false;
used[i] = 1;
ans.emplace_back(cs[i].second, ds[j].second);
}
for (int i = 0; i < csLen; ++i) if (!used[i]) {
remain.push_back(cs[i].second);
}
}
for (int i = 0; i < tsLen; ) {
if (i + 1 < tsLen && ts[i].first == ts[i + 1].first) {
ans.emplace_back(ts[i].second, ts[i + 1].second);
i += 2;
} else {
remain.push_back(ts[i].second);
i += 1;
}
}
if (remain.size() >= 2) {
return false;
}
for (const int v : remain) {
if (!~P[u]) {
return false;
}
dp[P[u]].push_back(v);
}
}
puts("YES");
for (const auto &e : ans) {
printf("%d %d\n", e.first + 1, e.second + 1);
}
return true;
}
int main() {
char buf[110];
for (; ~scanf("%d", &N); ) {
P.assign(N, -1);
T.assign(N, '-');
for (int u = 1; u < N; ++u) {
scanf("%*d%d%s", &P[u], buf);
--P[u];
T[u] = buf[0];
}
const bool res = solve();
if (!res) {
puts("NO");
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3568kb
input:
8 2 1 - 3 1 - 4 2 Tong 5 2 Tong 6 3 Duan 7 3 - 8 7 Chang
output:
YES 8 6 4 5
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 2ms
memory: 3600kb
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 8 9 10 3 6 2 5 7
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 2ms
memory: 3536kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 20ms
memory: 8868kb
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.