QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#252914#6396. Puzzle: KusabisupepapupuWA 30ms14596kbC++171.9kb2023-11-16 14:49:522023-11-16 14:49:52

Judging History

你现在查看的是最新测评结果

  • [2023-11-16 14:49:52]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:14596kb
  • [2023-11-16 14:49:52]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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.