QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#378441#6396. Puzzle: KusabilingWA 43ms38356kbC++173.1kb2024-04-06 13:02:142024-04-06 13:02:15

Judging History

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

  • [2024-04-06 13:02:15]
  • 评测
  • 测评结果:WA
  • 用时:43ms
  • 内存:38356kb
  • [2024-04-06 13:02:14]
  • 提交

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];
void dfs(ll u, ll fa)
{
    d[u] = d[fa] + 1;
    for (auto &v : g[u])
    {
        if (v == fa)
            continue;
        dfs(v, u);
    }
}
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[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    vector<pll> chang, duan, tong;
    FOR(i, 1, n)
    {
        if (a[i] == 1)
            chang.push_back({d[i], i});
        else if (a[i] == 2)
            duan.push_back({d[i], i});
        else if (a[i] == 3)
            tong.push_back({d[i], i});
    }
    if (tong.size() % 2 || chang.size() != duan.size())
    {
        cout << "NO" << edl;
        return;
    }
    sort(chang.begin(), chang.end());
    sort(duan.begin(), duan.end());
    sort(tong.begin(), tong.end());

    vector<pll> ans;
    FOR(i, 0, tong.size() - 1)
    {
        if (tong[i].first != tong[i + 1].first)
        {
            cout << "NO" << edl;
            return;
        }
        else
            ans.push_back({tong[i].second, tong[i + 1].second});
        ++i;
    }
    FOR(i, 0, duan.size() - 1)
    {
        if (duan[i].first >= chang[i].first)
        {
            cout << "NO" << edl;
            return;
        }
        else
            ans.push_back({duan[i].second, chang[i].second});
    }
    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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

YES
4 5
6 8

result:

ok Correct.

Test #2:

score: 0
Accepted
time: 4ms
memory: 30500kb

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
2 6
7 5
3 10

result:

ok Correct.

Test #3:

score: 0
Accepted
time: 4ms
memory: 29408kb

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 43ms
memory: 38356kb

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.