QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#378781 | #6396. Puzzle: Kusabi | ling | WA | 19ms | 33636kb | C++17 | 3.6kb | 2024-04-06 14:37:33 | 2024-04-06 14:37:34 |
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});
}
vector<pll> ve;
while (q[3].size())
{
pll x = q[3].top();
q[3].pop();
if (q[3].size() == 0)
{
ve.push_back(x);
break;
}
pll y = q[3].top();
q[3].pop();
if (x.first == y.first)
ans.push_back({x.second, y.second});
else
{
ve.push_back(x);
q[3].push(y);
}
}
// dbg(u);
// dbg(ve);
if (abs((ll)q[1].size() - (ll)q[2].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)
{
ve.push_back(x);
q[2].push(y);
}
else
ans.push_back({x.second, y.second});
}
if (q[1].size())
ve.push_back(q[1].top());
if (q[2].size())
ve.push_back(q[2].top());
// dbg(ve);
if (ve.size() > 1)
{
cout << "NO" << edl;
exit(0);
}
if (ve.size())
return ve[0].second;
else
return 0;
}
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: 30208kb
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: 2ms
memory: 29976kb
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: 4ms
memory: 30064kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 19ms
memory: 33636kb
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.