QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#378699 | #6396. Puzzle: Kusabi | ling | WA | 27ms | 30388kb | C++17 | 3.4kb | 2024-04-06 14:15:34 | 2024-04-06 14:15:36 |
Judging History
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.