QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#528581#6396. Puzzle: Kusabimegumi#WA 1ms9784kbC++144.3kb2024-08-23 16:28:582024-08-23 16:28:59

Judging History

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

  • [2024-08-23 16:28:59]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:9784kb
  • [2024-08-23 16:28:58]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
inline int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
        f = (c == '-') ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9')
        x = x * 10 + c - 48, c = getchar();
    return f * x;
}
const int N = 1e5 + 10;
int head[N], cnt;
struct edge {
    int to, next;
} edge[N << 2];
void add(int u, int v) {
    edge[++cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
int dep[N], cc[N],
    tt[N]; // 每个点的深度 每个点传上来的数据的深度 传上来的数据对应的点的编号
char a[N];
pair<char, int> P[N];
pair<int, int> ans[N];
int tr, mx;
void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    vector<pair<int, int>> vv[3]; // 分别存子树传上来的长短同
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (v == fa)
            continue;
        dfs(v, u);
        if (!tr)
            return;
        if (a[v] == 'C')
            vv[0].push_back({cc[v], tt[v]});
        else if (a[v] == 'D')
            vv[1].push_back({cc[v], tt[v]});
        else if (a[v] == 'T')
            vv[2].push_back({cc[v], tt[v]});
    }
    if (a[u] == 'C')
        vv[0].push_back({dep[u], u});
    else if (a[u] == 'D')
        vv[1].push_back({dep[u], u});
    else if (a[u] == 'T')
        vv[2].push_back({dep[u], u});
    sort(vv[0].begin(), vv[0].end());
    sort(vv[1].begin(), vv[1].end());
    sort(vv[2].begin(), vv[2].end());
    int len0 = vv[0].size(), len1 = vv[1].size(), len2 = vv[2].size();
    int flag = -1;
    if ((len0 + len1) % 2 + len2 % 2 == 2) {
        tr = 0;
        return;
    }
    if (abs(len0 - len1) >= 2) {
        tr = 0;
        return;
    }
    a[u] = '-';
    for (int i = 0; i < len2; i += 2) {
        if (i == len2 - 1 || vv[2][i].first != vv[2][i + 1].first) {
            if (flag != -1) {
                tr = 0;
                return;
            }
            flag = i, i--;
            continue;
        }
        ans[++mx] = {vv[2][i].second, vv[2][i + 1].second};
    }
    if (len2 % 2 == 0 && flag != -1) {
        tr = 0;
        return;
    } else if (flag != -1) {
        a[u] = 'T';
        cc[u] = vv[2][flag].first;
        tt[u] = vv[2][flag].second;
    }
    if (len0 == len1) {
        for (int i = 0; i < len0; i++) {
            if (vv[0][i].first <= vv[1][i].first) {
                tr = 0;
                return;
            }
            ans[++mx] = {vv[0][i].second, vv[1][i].second};
        }
        return;
    }

    if (len0 > len1) { // 长多
        int r = 0;
        a[u] = 'C';
        int flag = len0 - 1;
        for (int i = 0; i < len1; i++) {
            while (vv[0][r].first <= vv[1][i].first && r < len0) {
                r++;
                flag = r;
                if (r == len0) {
                    tr = 0;
                    return;
                }
            }
            ans[++mx] = {vv[0][i].second, vv[1][r].second};
            r++;
            if (r > len0) {
                tr = 0;
                return;
            }
        }
        cc[u] = vv[0][flag].first;
        tt[u] = vv[0][flag].second;
    }

    else { // 短多
        a[u] = 'D';
        int r = len1 - 1, flag = 0;
        for (int i = len0 - 1; i >= 0; i--) {
            if (r == -1) {
                tr = 0;
                return;
            }
            while (vv[0][i].first <= vv[1][r].first) {
                flag = r;
                r--;
                if (r == -1) {
                    tr = 0;
                    return;
                }
            }
            ans[++mx] = {vv[0][i].second, vv[1][r].second};
            r--;
        }
        cc[u] = vv[1][flag].first;
        tt[u] = vv[1][flag].second;
    }
}
signed main() {
    int n;
    n = read();
    string s;
    tr = 1;
    for (int i = 1; i < n; i++) {
        int u = read(), fa = read();
        cin >> s;
        add(fa, u);
        a[u] = s[0];
    }
    dep[1] = 1;
    dfs(1, 0);
    if (!tr)
        cout << "NO\n";
    else {
        cout << "YES\n";
        for (int i = 1; i <= mx; i++) {
            cout << ans[i].first << ' ' << ans[i].second << "\n";
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 9784kb

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: 1ms
memory: 9772kb

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: -100
Wrong Answer
time: 0ms
memory: 7724kb

input:

2
2 1 Tong

output:

YES

result:

wrong answer Only odd number of marked vertices to match.