QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#252914 | #6396. Puzzle: Kusabi | supepapupu | WA | 30ms | 14596kb | C++17 | 1.9kb | 2023-11-16 14:49:52 | 2023-11-16 14:49:52 |
Judging History
answer
#include <bits/stdc++.h>
#define x first
#define y second
#define el '\n'
#define debug(x) cout << #x << ": " << x << el
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 3e5 + 10, INF = 0x3f3f3f3f, mod = 998244353;
void inc(ll &a, ll b) {
a += b;
if (a >= mod) a -= mod;
}
void dec(ll &a, ll b) {
a -= b;
if (a < 0) a += mod;
}
ll add(ll a, ll b) {
a += b;
return a >= mod ? a - mod : a;
}
ll del(ll a, ll b) {
a -= b;
return a < 0 ? a + mod : a;
}
vector<int> G[N];
vector<int> chang, duan, tong;
int dep[N];
void dfs(int u, int fa) {
dep[u] = dep[fa] + 1;
for (int v: G[u]) dfs(v, u);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
for (int i = 1; i < n; ++i) {
int a, b; string str; cin >> a >> b >> str;
if (str == "Chang") chang.emplace_back(a);
else if (str == "Duan") duan.emplace_back(a);
else if (str == "Tong") tong.emplace_back(a);
G[b].emplace_back(a);
}
dfs(1, 0);
vector<pii> sc, sd, st;
for (auto a: chang) sc.emplace_back(dep[a], a);
for (auto a: duan) sd.emplace_back(dep[a], a);
for (auto a: tong) st.emplace_back(dep[a], a);
vector<pii> ans;
if (st.size() & 1) return cout << "NO\n", 0;
if (sc.size() != sd.size()) return cout << "NO\n", 0;
sort(st.begin(), st.end()), sort(sc.begin(), sc.end()), sort(sd.begin(), sd.end());
for (int i = 0; i < st.size(); i += 2) {
if (st[i].x != st[i + 1].x) return cout << "NO\n", 0;
ans.emplace_back(st[i].y, st[i + 1].y);
}
for (int i = 0; i < sc.size(); ++i) {
if (sc[i].x <= sd[i].x) return cout << "NO\n", 0;
ans.emplace_back(sc[i].y, sd[i].y);
}
cout << "YES\n";
for (auto[a, b]: ans) cout << a << ' ' << b << el;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 11564kb
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: 10544kb
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 6 2 5 7 10 3
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 11568kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 30ms
memory: 14596kb
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:
YES 28763 61327 78961 79617 3156 3283 3681 7241 8241 8873 14132 15911 19874 24772 27446 28194 31315 33789 41090 52589 58699 59851 69010 69894 78400 79799 83333 85932 93895 95031 309 2042 2267 2564 3328 3940 5219 5411 6257 6310 7602 7965 8051 8063 10051 10294 10691 11158 13236 13533 14566 15047 15407...
result:
wrong answer Edge 59423-1 used twice.