QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#378441 | #6396. Puzzle: Kusabi | ling | WA | 43ms | 38356kb | C++17 | 3.1kb | 2024-04-06 13:02:14 | 2024-04-06 13:02:15 |
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];
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.