QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#379182 | #6396. Puzzle: Kusabi | AINgray | WA | 40ms | 11796kb | C++23 | 5.6kb | 2024-04-06 16:31:14 | 2024-04-06 16:31:15 |
Judging History
answer
// #define NDEBUG
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
using db = double;
void Main(void);
int main(void)
{
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#if defined(TEXT_IO) and defined(LOCAL) and not defined(ONLINE_JUDGE)
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
Main();
return 0;
}
/**************************************************/
namespace my
{
#if defined(LOCAL) and not defined(ONLINE_JUDGE)
#include "D:\VScodeFile\LOCAL\debug.h"
#define DBG(x) std::cerr << "! " #x " = " << (x) << std::endl
#else
#define dbg(...) ((void)0)
#define DBG(...) ((void)0)
#endif
#define VE std::vector
#define STR std::string
#define HEAP std::priority_queue
#define PLL std::pair<ll, ll>
#define fi first
#define se second
#define EDL '\n'
#define WS ' '
#define SDP(x) std::fixed << std::setprecision(x)
#define SZ(x) ((ll)x.size())
#define FOR(i, l, r) for (ll i = (l); i <= (r); ++i)
#define ROF(i, r, l) for (ll i = (r); i >= (l); --i)
constexpr int inf = 0x3f3f3f3f;
constexpr long long INF = 0x3f3f3f3f3f3f3f3fLL;
constexpr db EPS = 1.0e-9;
constexpr ll MOD2 = 1e9 + 7;
constexpr ll MOD = 998244353;
constexpr ll SZ2 = 1e3 + 3;
constexpr ll SZ = 2e5 + 5;
}
using namespace my;
namespace fastIO
{
constexpr ll BUF_SZ = 1e5 + 5;
bool IOrun = true;
char NC(void)
{
static char buf[BUF_SZ], *p = buf + BUF_SZ, *ed = buf + BUF_SZ;
if (p != ed)
return *p++;
p = buf;
ed = buf + fread(buf, 1, BUF_SZ, stdin);
if (p == ed)
{
IOrun = false;
return -1;
}
return *p++;
}
bool BLK(char c) { return c == WS or c == EDL or c == '\r' or c == '\t'; }
template <class T>
bool FIN(T &x)
{
bool sign = false;
char c = NC();
x = 0;
while (BLK(c))
c = NC();
if (not IOrun)
return false;
if (c == '-')
{
sign = true;
c = NC();
}
while ('0' <= c and c <= '9')
{
x = x * 10 + c - '0';
c = NC();
}
if (sign)
x = -x;
return true;
}
bool FIN(db &x)
{
bool sign = false;
char c = NC();
x = 0;
while (BLK(c))
c = NC();
if (not IOrun)
return false;
if (c == '-')
{
sign = true;
c = NC();
}
while ('0' <= c and c <= '9')
{
x = x * 10 + c - '0';
c = NC();
}
if (c == '.')
{
db w = 1.0;
c = NC();
while ('0' <= c and c <= '9')
{
w /= 10.0;
x += w * (c - '0');
c = NC();
}
}
if (sign)
x = -x;
return true;
}
bool FIN(char &c)
{
c = NC();
while (BLK(c))
c = NC();
if (not IOrun)
{
c = -1;
return false;
}
return true;
}
bool FIN(char *s)
{
char c = NC();
while (BLK(c))
c = NC();
if (not IOrun)
return false;
while (IOrun and not BLK(c))
{
*s++ = c;
c = NC();
}
*s = 0;
return true;
}
bool LIN(char *s)
{
char c = NC();
while (BLK(c))
c = NC();
if (not IOrun)
return false;
while (IOrun and c != EDL)
{
*s++ = c;
c = NC();
}
*s = 0;
return true;
}
template <class T, class... Y>
bool FIN(T &x, Y &...o) { return FIN(x) and FIN(o...); }
void FIN(ll *a, ll l, ll r)
{
FOR(i, l, r)
FIN(a[i]);
return;
}
void FIN(db *a, ll l, ll r)
{
FOR(i, l, r)
FIN(a[i]);
return;
}
void FIN(char *a, ll l, ll r)
{
FOR(i, l, r)
FIN(a[i]);
return;
}
}
using fastIO::FIN;
using fastIO::LIN;
/**************************************************/
ll n;
VE<ll> E[SZ];
ll kind[SZ];
ll deep[SZ];
ll unsure[SZ];
bool ok;
VE<PLL> ans;
void DFS_DEP(ll x)
{
for (const auto &son : E[x])
{
deep[son] = deep[x] + 1;
DFS_DEP(son);
}
return;
}
bool CMP(const ll &lh, const ll &rh)
{
if (deep[lh] != deep[rh])
return deep[lh] < deep[rh];
return kind[lh] < kind[rh];
}
void DFS(ll x)
{
for (const auto &son : E[x])
DFS(son);
VE<ll> wait;
for (const auto &son : E[x])
if (unsure[son] != 0 and kind[unsure[son]] == 3)
wait.push_back(unsure[son]);
if (kind[x] == 3)
wait.push_back(x);
std::sort(wait.begin(), wait.end(), CMP);
ll p = 0, lim = SZ(wait) - 1;
while (p <= lim)
{
if (p + 1 <= lim and deep[wait[p]] == deep[wait[p + 1]])
{
ans.push_back({wait[p], wait[p + 1]});
p += 2;
}
else if (unsure[x] == 0)
{
unsure[x] = wait[p];
++p;
}
else
{
ok = false;
return;
}
}
wait.clear();
for (const auto &son : E[x])
if (unsure[son] != 0 and (kind[unsure[son]] == 1 or kind[unsure[son]] == 2))
wait.push_back(unsure[son]);
if (kind[x] == 1 or kind[x] == 2)
wait.push_back(x);
std::sort(wait.begin(), wait.end(), CMP);
std::queue<ll> qu;
for (const auto &ele : wait)
if (kind[ele] == 2)
qu.push(ele);
else
{
if (qu.empty())
{
if (unsure[x] == 0)
unsure[x] = ele;
else
{
ok = false;
return;
}
}
else
{
ll aim = qu.front();
qu.pop();
ans.push_back({ele, aim});
}
}
while (not qu.empty())
{
ll aim = qu.front();
qu.pop();
if (unsure[x] == 0)
unsure[x] = aim;
else
{
ok = false;
return;
}
}
return;
}
void Main(void)
{
cin >> n;
FOR(ni, 1, n - 1)
{
ll i, pi;
STR ti;
cin >> i >> pi >> ti;
E[pi].push_back(i);
if (ti[0] == 'C')
kind[i] = 1;
else if (ti[0] == 'D')
kind[i] = 2;
else if (ti[0] == 'T')
kind[i] = 3;
}
DFS_DEP(1);
ok = true;
DFS(1);
if (unsure[1] or not ok)
{
cout << "NO" << EDL;
return;
}
cout << "YES" << EDL;
for (const auto &[u, v] : ans)
cout << u << WS << v << EDL;
return;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5660kb
input:
8 2 1 - 3 1 - 4 2 Tong 5 2 Tong 6 3 Duan 7 3 - 8 7 Chang
output:
YES 4 5 8 6
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 1ms
memory: 7932kb
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 8 9 6 2 5 7
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 40ms
memory: 11796kb
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.