QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#378699#6396. Puzzle: KusabilingWA 27ms30388kbC++173.4kb2024-04-06 14:15:342024-04-06 14:15:36

Judging History

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

  • [2024-04-06 14:15:36]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:30388kb
  • [2024-04-06 14:15:34]
  • 提交

answer

//(ᗜ ˰ ᗜ)
// #define NDEBUG
#include <bits/stdc++.h>
using namespace std;
namespace LING
{
#ifdef ONLINE_JUDGE
#define DBG(...) ;
#define dbg(...) ;
#else
#define DBG(x) cout << "! " << #x << " = " << x << endl
#include "debug.h"
#endif
    using ll = long long;
    using db = double;
#define SPO(x) fixed << setprecision(x)
#define FOR(i, l, r) for (ll i = l; i <= (r); ++i)
#define ROF(i, r, l) for (ll i = r; i >= (l); --i)
#define edl '\n'
#define fir first
#define sec second
#define str string
#define pll pair<ll, ll>
#define heap priority_queue
    // constexpr db PI = acos(-1.0);
    // constexpr db EPS = 1.0e-9;
    constexpr long long LNF = 0x3f3f3f3f3f3f3f3fLL;
    constexpr int INF = 0x3f3f3f3f;
    constexpr long long MOD = 998244353;
    constexpr ll MXN = 1e6 + 5;
    ll KSM(ll base, ll exp, ll MOD)
    {
        ll res = 1;
        base %= MOD;
        while (exp)
        {
            if (exp & 1)
                res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp >>= 1;
        }
        return res;
    }
}
using namespace LING;
ll n;
ll a[MXN];
ll d[MXN];
vector<ll> g[MXN];
vector<pll> ans;
void dfs(ll u)
{
    for (auto &v : g[u])
    {
        d[v] = d[u] + 1;
        dfs(v);
    }
}
ll dfs1(ll u)
{
    heap<pll> q[4];
    if (a[u])
        q[a[u]].push({d[u], u});
    for (auto &v : g[u])
    {
        d[v] = d[u] + 1;
        ll tmp = dfs1(v);
        if (tmp)
            q[a[tmp]].push({d[tmp], tmp});
    }
    // dbg(u);
    // dbg(q[1]);
    // dbg(q[2]);
    // dbg(q[3]);
    while (q[3].size())
    {
        if (q[3].size() == 1)
            break;
        pll x = q[3].top();
        q[3].pop();
        pll y = q[3].top();
        q[3].pop();
        if (x.first == y.first)
            ans.push_back({x.second, y.second});
    }
    if (abs((ll)q[1].size() - (ll)q[2].size()) + q[3].size() > 1)
    {
        cout << "NO" << edl;
        exit(0);
    }
    while (q[1].size() && q[2].size())
    {
        pll x = q[1].top();
        q[1].pop();
        pll y = q[2].top();
        q[2].pop();
        if (x.first <= y.first)
        {
            cout << "NO" << edl;
            exit(0);
        }
        ans.push_back({x.second, y.second});
    }
    // dbg(q[1]);
    // dbg(q[2]);
    // dbg(q[3]);
    ll res = 0;
    FOR(i, 1, 3)
    {
        if (q[i].size())
            res = q[i].top().second;
    }
    return res;
}
void Solve(void)
{
    cin >> n;
    FOR(i, 2, n)
    {
        ll u, v, w;
        str t;
        cin >> u >> v >> t;
        if (t == "Chang")
            w = 1;
        else if (t == "Duan")
            w = 2;
        else if (t == "Tong")
            w = 3;
        else
            w = 0;
        a[u] = w;
        g[v].push_back(u);
    }
    dfs(1);

    // FOR(i, 1, n)
    // cout << d[i] << " \n"[i == n];

    if (dfs1(1))
        cout << "NO" << edl;
    else
    {
        cout << "YES" << edl;
        for (auto &i : ans)
            cout << i.first << ' ' << i.second << edl;
    }
    return;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // #ifndef ONLINE_JUDGE
    // freopen("cin.txt","r",stdin);
    // freopen("cout.txt","w",stdout);
    // #endif

    int t = 1;
    // cin >> t;
    while (t--)
        Solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 26948kb

input:

8
2 1 -
3 1 -
4 2 Tong
5 2 Tong
6 3 Duan
7 3 -
8 7 Chang

output:

YES
5 4
8 6

result:

ok Correct.

Test #2:

score: 0
Accepted
time: 3ms
memory: 27280kb

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
9 8
5 2
6 7

result:

ok Correct.

Test #3:

score: 0
Accepted
time: 0ms
memory: 27076kb

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 27ms
memory: 30388kb

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.