QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#186204#6396. Puzzle: KusabiUESTC_Guest_WiFiWA 37ms64768kbC++172.7kb2023-09-23 13:04:482023-09-23 13:04:48

Judging History

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

  • [2023-09-23 13:04:48]
  • 评测
  • 测评结果:WA
  • 用时:37ms
  • 内存:64768kb
  • [2023-09-23 13:04:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double;
const int N = 2e5 + 50;

using pii = pair<int, int>;
vector<pii> ans;
int n;
int t[N];
vector<int> e[N];
vector<int> depnodes[N];
int dep[N], mx_dep;

multiset<pii> s[5][N];

void dfs(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    depnodes[dep[u]].push_back(u);
    for (auto v : e[u])
    {
        if (v == fa)
            continue;
        dfs(v, u);
    }
}

void work(int depth)
{
    for (auto u : depnodes[depth])
    {
        for (auto v : e[u])
        {
            if (dep[v] < dep[u])
                continue;
            for (int i = 1; i <= 3; i++)
            {
                for (auto k : s[i][v])
                    s[i][u].insert(k);
                s[i][v].clear();
            }
        }
        if (t[u])
            s[t[u]][u].insert(make_pair(depth, u));
        for (auto it = s[1][u].begin(); it != s[1][u].end() && !s[2][u].empty();)
        {
            auto it2 = s[2][u].lower_bound(*it);
            if (it2 != s[2][u].begin())
            {
                it2--;
                if (it2->first < it->first)
                {
                    ans.emplace_back(it->second, it2->second);
                    it = s[1][u].erase(it);
                    s[2][u].erase(it2);
                }
                else
                    it = next(it);
            }
            else
                it = next(it);
        }
        for (auto it = s[3][u].begin(); it != s[3][u].end() && next(it) != s[3][u].end();)
        {
            if (dep[it->second] == dep[next(it)->second])
            {
                ans.emplace_back(it->second, next(it)->second);
                it = s[3][u].erase(it);
                it = s[3][u].erase(it);
            }
            else
                it = next(it);
        }
        int sum_sz = 0;
        for (int i = 1; i <= 3; i++)
            sum_sz += s[i][u].size();
        if ((sum_sz >= 2) || (u == 1 && sum_sz >= 1))
        {
            cout << "NO\n";
            exit(0);
        }
    }
}

int main()
{
    scanf("%d", &n);
    int cnt_spec = 0;
    for (int i = 1; i < n; i++)
    {
        int ni, pi;
        char ti[10] = {0};
        scanf("%d%d%s", &ni, &pi, ti);
        t[ni] = (ti[0] == 'C' ? 1 : (ti[0] == 'D' ? 2 : (ti[0] == 'T' ? 3 : 0)));
        e[ni].push_back(pi), e[pi].push_back(ni);
        cnt_spec += (ti[0] != '-');
    }
    // if (cnt_spec % 2)
    //     return printf("NO\n"), 0;

    dfs(1, 0);
    mx_dep = *max_element(dep, dep + N);

    for (int d = mx_dep; d >= 1; d--)
        work(d);

    printf("YES\n");
    for (auto [x, y] : ans)
        printf("%d %d\n", x, y);

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 61204kb

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: 8ms
memory: 60924kb

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

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 37ms
memory: 64768kb

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.