QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#379185 | #6396. Puzzle: Kusabi | AINgray | AC ✓ | 40ms | 36556kb | C++23 | 5.6kb | 2024-04-06 16:31:37 | 2024-04-06 16:31:37 |
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::stack<ll> st;
for (const auto &ele : wait)
if (kind[ele] == 2)
st.push(ele);
else
{
if (st.empty())
{
if (unsure[x] == 0)
unsure[x] = ele;
else
{
ok = false;
return;
}
}
else
{
ll aim = st.top();
st.pop();
ans.push_back({ele, aim});
}
}
while (not st.empty())
{
ll aim = st.top();
st.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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5668kb
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: 5688kb
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: 3644kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: 0
Accepted
time: 34ms
memory: 10692kb
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 46666 56115 88119 38802 93143 10006 31531 76473 42604 15988 6569 30148 11412 2008 64525 46703 71289 70618 81204 47748 42353 20514 97634 46131 83516 82155 66867 62410 15712 9975 4978 3205 83026 5622 48783 10902 82167 30893 93809 65878 33377 66951 94549 66936 79128 64411 8453 22475 54702 36857 629...
result:
ok Correct.
Test #5:
score: 0
Accepted
time: 31ms
memory: 11700kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 4 - 7 6 - 8 7 - 9 5 - 10 9 - 11 10 - 12 6 - 13 12 - 14 11 - 15 9 - 16 14 - 17 16 - 18 10 - 19 15 - 20 13 - 21 20 - 22 17 - 23 22 - 24 22 Duan 25 11 - 26 12 - 27 20 - 28 18 - 29 28 - 30 16 - 31 28 - 32 30 - 33 31 - 34 28 - 35 34 - 36 35 - 37 22 - 38 34 - 39 38 - 40 35...
output:
YES 28541 5203 5981 8106 7900 7551 53424 47998 91669 86909 40295 72002 65376 32334 95652 57528 66693 91216 88445 98194 54118 44959 76761 74202 71470 64661 85084 30271 60344 41192 41421 10342 79425 12876 35989 25933 41959 39297 94979 46303 46189 10581 51797 14956 82599 41806 26090 60566 94132 48923 7...
result:
ok Correct.
Test #6:
score: 0
Accepted
time: 40ms
memory: 10972kb
input:
100000 2 1 - 3 2 - 4 3 Duan 5 4 Chang 6 5 Duan 7 6 Chang 8 7 Duan 9 8 Chang 10 9 Duan 11 10 Chang 12 11 Duan 13 12 Chang 14 12 Duan 15 14 Chang 16 15 Tong 17 15 Tong 18 17 Duan 19 18 Duan 20 19 Chang 21 18 Duan 22 21 Duan 23 18 Chang 24 21 - 25 24 Duan 26 25 Chang 27 26 Duan 28 27 Chang 29 26 Duan 3...
output:
YES 20 19 65 55 53 52 48 46 36 35 34 22 61 58 57 56 1206 1097 1593 1522 1938 1890 1365 1217 1295 1191 2188 2158 2845 1764 1646 1408 5721 3147 2810 2746 3194 2937 2399 2710 3778 3657 3580 2668 2179 2259 2174 2122 2379 2204 2449 2392 2499 2218 2369 2233 2077 2020 9174 8244 15184 14498 15193 14362 1069...
result:
ok Correct.
Test #7:
score: 0
Accepted
time: 34ms
memory: 11724kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 5 - 7 6 - 8 7 - 9 8 - 10 9 Duan 11 10 - 12 11 Chang 13 12 Duan 14 13 Chang 15 14 - 16 15 - 17 16 Duan 18 17 Chang 19 17 - 20 19 - 21 20 - 22 21 - 23 22 - 24 23 - 25 24 - 26 25 Duan 27 26 - 28 27 Duan 29 28 - 30 29 Chang 31 28 - 32 31 Chang 33 32 - 34 32 - 35 34 - 36 ...
output:
YES 85 81 105 107 103 117 172 168 275 273 333 321 384 369 327 314 463 433 429 437 588 543 639 667 1273 1167 1375 1160 1176 1117 995 1021 929 926 1059 832 1242 1196 1328 1329 1259 1254 1213 1194 1275 1150 1689 1521 1620 1424 1229 1226 1277 1134 1099 915 1237 1218 1358 1316 1350 1284 2524 2462 2335 21...
result:
ok Correct.
Test #8:
score: 0
Accepted
time: 30ms
memory: 12028kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 5 Duan 7 6 - 8 7 - 9 8 - 10 9 Chang 11 10 - 12 11 Duan 13 12 Chang 14 13 - 15 14 Duan 16 15 Chang 17 16 - 18 17 - 19 18 Duan 20 19 - 21 20 - 22 21 - 23 22 Chang 24 23 - 25 24 Duan 26 25 - 27 26 Chang 28 27 - 29 28 - 30 29 - 31 30 Duan 32 31 - 33 32 - 34 33 - 35 34 - ...
output:
YES 69 68 120 118 237 227 225 221 265 266 323 314 309 304 346 343 352 345 338 341 350 347 401 392 439 436 471 469 474 473 472 463 482 480 499 495 483 477 570 567 613 604 588 584 577 576 744 738 743 739 732 730 851 848 841 809 886 881 930 911 951 947 1029 1007 1002 964 958 946 919 914 942 939 959 952...
result:
ok Correct.
Test #9:
score: 0
Accepted
time: 34ms
memory: 11180kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 5 Duan 7 6 - 8 7 - 9 8 Chang 10 9 - 11 10 Duan 12 11 - 13 12 Chang 14 13 Duan 15 14 - 16 15 Chang 17 16 - 18 17 Duan 19 18 - 20 19 Chang 21 20 Duan 22 21 Chang 23 22 - 24 23 Duan 25 24 Chang 26 25 Duan 27 26 - 28 27 - 29 28 Chang 30 29 Duan 31 30 Chang 32 31 - 33 32 ...
output:
YES 239 238 274 272 344 343 416 415 433 432 478 477 515 512 544 539 582 579 633 631 711 700 724 717 730 719 787 784 782 780 772 773 783 777 830 831 821 824 816 810 845 849 860 858 872 868 895 897 894 876 871 873 936 929 999 986 984 981 980 976 966 964 955 950 967 958 977 968 997 996 995 993 1039 103...
result:
ok Correct.
Test #10:
score: 0
Accepted
time: 25ms
memory: 12644kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 5 - 7 6 - 8 7 - 9 8 - 10 9 - 11 10 - 12 11 - 13 12 - 14 13 - 15 14 - 16 15 - 17 16 - 18 17 - 19 18 - 20 19 - 21 20 - 22 21 - 23 22 - 24 23 - 25 24 - 26 25 - 27 26 - 28 27 - 29 28 - 30 29 - 31 30 - 32 31 - 33 32 - 34 33 - 35 34 - 36 35 - 37 36 - 38 37 - 39 38 - 40 39 ...
output:
YES 4986 4915 6738 6570 14195 13597 22308 22019 31800 31792 38186 38225 43898 43803 41864 41995 42725 42327 43871 43807 43953 43542 46356 46361 47755 47608 47521 46932 46885 44955 48399 48486 50116 49839 49912 49668 54823 53355 54714 54273 54239 53853 52947 52524 57456 55640 58348 58053 59658 59228 ...
result:
ok Correct.
Test #11:
score: 0
Accepted
time: 25ms
memory: 10568kb
input:
100000 2 1 - 3 1 - 4 2 - 5 1 - 6 1 - 7 2 Duan 8 4 - 9 1 - 10 1 - 11 2 - 12 2 - 13 2 - 14 6 - 15 1 - 16 6 - 17 1 - 18 5 - 19 1 - 20 1 - 21 2 - 22 8 - 23 6 - 24 1 - 25 4 Duan 26 1 - 27 10 - 28 1 - 29 8 - 30 5 - 31 7 - 32 2 - 33 3 - 34 12 - 35 3 - 36 1 - 37 12 - 38 8 - 39 8 - 40 1 - 41 4 - 42 16 - 43 8...
output:
YES 34242 34406 14906 23870 28768 79207 50509 68052 70759 32304 70523 36687 36153 68751 47669 3567 18177 70173 50978 58218 27598 56574 46683 47073 79895 6904 85751 4139 83196 17677 65881 90916 44928 67031 49996 25922 28068 95211 43712 69374 84697 19260 32128 70765 30451 79850 92289 12144 99611 51006...
result:
ok Correct.
Test #12:
score: 0
Accepted
time: 16ms
memory: 8428kb
input:
100000 2 1 - 3 1 - 4 1 - 5 1 - 6 1 - 7 1 - 8 1 - 9 1 - 10 3 - 11 1 - 12 2 - 13 2 - 14 2 - 15 1 - 16 2 - 17 2 - 18 1 - 19 1 - 20 1 - 21 2 - 22 1 - 23 2 - 24 2 - 25 1 - 26 1 - 27 4 - 28 1 - 29 2 - 30 3 - 31 1 - 32 10 - 33 6 - 34 4 - 35 1 - 36 2 Duan 37 1 - 38 4 - 39 10 - 40 1 - 41 1 - 42 3 - 43 6 - 44...
output:
YES 15102 66302 37177 40113 67735 67876 70745 98880 75547 84740 88398 71830 62593 85699 71970 21755 94458 6455 74239 39981 71421 13515 37672 71660 90862 91238 42744 19470 13573 72747 10218 81223 15063 87004 19357 68085 44673 6427 92721 4280 17731 33161 45357 358 49326 65914 45470 93622 91832 15964 9...
result:
ok Correct.
Test #13:
score: 0
Accepted
time: 29ms
memory: 8252kb
input:
100000 2 1 Duan 3 1 Duan 4 1 Duan 5 1 Duan 6 1 Duan 7 1 - 8 1 Duan 9 1 Duan 10 1 - 11 1 Duan 12 1 - 13 1 Duan 14 1 Duan 15 1 Duan 16 1 Duan 17 1 Duan 18 2 - 19 1 Duan 20 1 Duan 21 2 - 22 2 Duan 23 1 Duan 24 1 Duan 25 1 Duan 26 1 Duan 27 2 Duan 28 1 Duan 29 2 Duan 30 1 Duan 31 2 Duan 32 1 - 33 1 Duan...
output:
YES 63894 95158 88697 88086 85544 75216 73765 72642 72241 69085 14063 61983 55203 54430 50491 41588 40110 38849 34955 27596 15274 1136 10786 18595 21493 24025 25178 30164 30800 40282 50699 52476 59910 76452 79238 86389 91441 96792 30463 1197 34098 46043 47433 49151 56601 57549 59254 65754 66989 8754...
result:
ok Correct.
Test #14:
score: 0
Accepted
time: 21ms
memory: 8296kb
input:
100000 2 1 - 3 1 - 4 1 - 5 1 - 6 1 - 7 1 - 8 1 - 9 1 - 10 1 - 11 1 - 12 1 - 13 1 Duan 14 1 - 15 1 - 16 1 - 17 1 - 18 1 - 19 1 - 20 1 - 21 1 - 22 1 - 23 1 - 24 1 - 25 1 - 26 1 - 27 1 - 28 1 - 29 1 Duan 30 1 - 31 1 - 32 2 Duan 33 1 - 34 1 - 35 1 Duan 36 1 - 37 1 - 38 1 - 39 1 - 40 1 - 41 1 - 42 1 - 43...
output:
YES 51260 62964 64799 73003 87232 98672 31245 38059 47626 58383 78385 82570 84269 91105 67893 90700 95599 97507 51711 96567 84425 2480 90521 97467 97387 3614 52378 20327 24851 31941 34768 35502 36133 37919 38081 41305 46820 47134 51834 18144 52602 53825 60150 63344 65516 68450 79862 84495 88745 9084...
result:
ok Correct.
Test #15:
score: 0
Accepted
time: 18ms
memory: 8500kb
input:
100000 2 1 Duan 3 1 - 4 1 - 5 1 Duan 6 1 - 7 1 - 8 1 - 9 1 - 10 1 - 11 1 - 12 1 - 13 1 - 14 1 - 15 1 - 16 1 - 17 1 - 18 1 - 19 1 - 20 1 - 21 1 - 22 1 - 23 1 - 24 1 - 25 1 - 26 1 - 27 1 - 28 1 - 29 1 - 30 1 - 31 1 - 32 1 - 33 1 Duan 34 1 - 35 1 - 36 1 - 37 1 - 38 1 - 39 1 - 40 1 - 41 1 - 42 1 - 43 1 ...
output:
YES 51853 97806 89831 81679 70717 62015 60751 59449 56321 54934 54125 53261 24271 49313 49018 46496 43803 39709 39458 38753 38738 38484 37384 32530 58304 99744 99690 97190 93135 88437 76662 73977 73029 71317 68370 61172 61007 58424 18859 57761 57280 55259 54712 46485 44356 43694 39921 34688 33247 30...
result:
ok Correct.
Test #16:
score: 0
Accepted
time: 18ms
memory: 8340kb
input:
100000 2 1 Duan 3 1 Duan 4 1 - 5 1 Duan 6 1 - 7 1 Duan 8 1 Duan 9 1 Duan 10 1 Duan 11 1 - 12 1 - 13 1 - 14 1 Duan 15 1 Duan 16 1 Duan 17 1 - 18 1 Duan 19 1 Duan 20 1 Duan 21 1 - 22 1 - 23 1 Duan 24 1 Duan 25 1 Duan 26 1 - 27 1 - 28 1 Duan 29 1 Duan 30 1 - 31 1 Duan 32 1 Duan 33 1 - 34 1 Duan 35 1 - ...
output:
YES 82705 336 60220 72014 80211 95022 93125 94029 59250 85950 77242 89854 56243 61755 80147 86382 86818 91748 37709 408 87876 89771 83493 452 97158 481 92488 614 95750 824 30379 31237 31218 31062 31048 30964 30860 30850 30689 30666 30642 30487 31450 30316 30298 30147 29890 29748 29745 29652 29648 29...
result:
ok Correct.
Test #17:
score: 0
Accepted
time: 33ms
memory: 10516kb
input:
100000 2 1 - 3 1 - 4 2 - 5 2 - 6 2 Duan 7 3 - 8 1 - 9 1 - 10 6 - 11 3 - 12 2 - 13 7 - 14 1 - 15 9 - 16 11 - 17 13 - 18 9 - 19 16 - 20 19 - 21 8 - 22 5 - 23 14 - 24 21 - 25 21 - 26 16 - 27 5 - 28 5 - 29 19 - 30 8 - 31 24 - 32 30 - 33 12 Duan 34 9 - 35 12 Duan 36 6 - 37 15 - 38 26 - 39 29 - 40 13 - 41...
output:
NO
result:
ok Correct.
Test #18:
score: 0
Accepted
time: 32ms
memory: 14036kb
input:
100000 2 1 Duan 3 2 Duan 4 3 - 5 3 Duan 6 4 - 7 4 Duan 8 3 Duan 9 2 - 10 4 Duan 11 8 Duan 12 6 - 13 3 Duan 14 6 Duan 15 7 Duan 16 6 Duan 17 14 Tong 18 7 - 19 16 Duan 20 14 Duan 21 12 Duan 22 20 Duan 23 14 Duan 24 19 - 25 2 Duan 26 22 - 27 24 Duan 28 8 Duan 29 4 Duan 30 23 Duan 31 24 Duan 32 23 Duan ...
output:
NO
result:
ok Correct.
Test #19:
score: 0
Accepted
time: 33ms
memory: 11692kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 5 - 7 4 - 8 7 - 9 8 - 10 9 - 11 10 Duan 12 9 - 13 12 - 14 12 - 15 10 - 16 8 - 17 13 - 18 10 - 19 14 - 20 13 - 21 19 - 22 19 Duan 23 11 - 24 23 Duan 25 23 - 26 5 - 27 22 - 28 22 Duan 29 17 - 30 29 - 31 29 - 32 17 - 33 27 - 34 33 Duan 35 31 - 36 24 - 37 34 - 38 37 - 39...
output:
NO
result:
ok Correct.
Test #20:
score: 0
Accepted
time: 26ms
memory: 10828kb
input:
100000 2 1 Duan 3 2 Chang 4 3 - 5 4 - 6 5 - 7 6 Duan 8 7 - 9 8 Chang 10 9 Duan 11 10 Chang 12 11 - 13 12 Duan 14 13 Chang 15 13 - 16 15 - 17 15 - 18 15 Duan 19 18 - 20 19 Duan 21 19 Chang 22 20 - 23 22 - 24 21 Duan 25 23 - 26 22 - 27 25 Chang 28 26 - 29 28 Duan 30 24 Chang 31 28 - 32 23 - 33 28 - 34...
output:
NO
result:
ok Correct.
Test #21:
score: 0
Accepted
time: 29ms
memory: 11564kb
input:
100000 2 1 Duan 3 2 Chang 4 3 - 5 4 - 6 5 Duan 7 6 - 8 7 - 9 8 Chang 10 9 Duan 11 10 Chang 12 11 Duan 13 12 Chang 14 12 - 15 14 - 16 15 Duan 17 16 Chang 18 17 - 19 17 Duan 20 19 - 21 19 Chang 22 21 - 23 21 Duan 24 23 Duan 25 24 Chang 26 24 Chang 27 24 Duan 28 27 - 29 28 Chang 30 28 Duan 31 30 - 32 3...
output:
NO
result:
ok Correct.
Test #22:
score: 0
Accepted
time: 35ms
memory: 11720kb
input:
100000 2 1 Duan 3 2 Chang 4 3 Duan 5 4 - 6 5 Chang 7 6 - 8 7 Duan 9 8 - 10 9 Chang 11 10 Duan 12 11 Chang 13 12 - 14 13 Duan 15 14 - 16 15 Chang 17 16 - 18 17 Duan 19 18 - 20 19 - 21 20 - 22 21 Chang 23 22 - 24 23 Duan 25 24 Chang 26 25 - 27 26 Duan 28 27 - 29 28 Chang 30 28 Duan 31 30 - 32 31 Chang...
output:
NO
result:
ok Correct.
Test #23:
score: 0
Accepted
time: 25ms
memory: 12132kb
input:
100000 2 1 Duan 3 2 - 4 3 - 5 4 - 6 5 - 7 6 - 8 7 - 9 8 - 10 9 - 11 10 - 12 11 Chang 13 12 Duan 14 13 - 15 14 - 16 15 Chang 17 16 Duan 18 17 Chang 19 18 - 20 19 - 21 20 - 22 21 - 23 22 - 24 23 - 25 24 - 26 25 Duan 27 26 - 28 27 - 29 28 - 30 29 - 31 30 - 32 31 - 33 32 - 34 33 Chang 35 34 - 36 35 - 37...
output:
NO
result:
ok Correct.
Test #24:
score: 0
Accepted
time: 29ms
memory: 12000kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 5 Duan 7 6 - 8 7 Chang 9 8 - 10 9 - 11 10 - 12 11 - 13 12 - 14 13 Duan 15 14 - 16 15 Chang 17 16 - 18 17 - 19 18 - 20 19 Duan 21 20 - 22 21 - 23 22 - 24 23 Chang 25 24 - 26 25 Duan 27 26 Chang 28 27 Duan 29 28 - 30 29 - 31 30 - 32 31 Chang 33 32 Duan 34 33 - 35 34 - ...
output:
NO
result:
ok Correct.
Test #25:
score: 0
Accepted
time: 21ms
memory: 9332kb
input:
100000 2 1 Duan 3 1 - 4 1 - 5 1 - 6 3 - 7 2 - 8 2 - 9 4 - 10 1 - 11 2 - 12 3 Duan 13 2 - 14 4 - 15 3 - 16 3 - 17 2 - 18 2 - 19 1 - 20 7 Duan 21 1 - 22 15 - 23 6 - 24 1 - 25 8 - 26 11 - 27 5 - 28 16 - 29 17 - 30 16 - 31 3 - 32 7 - 33 3 Duan 34 7 Duan 35 3 - 36 8 - 37 6 - 38 16 - 39 3 - 40 3 - 41 11 -...
output:
NO
result:
ok Correct.
Test #26:
score: 0
Accepted
time: 25ms
memory: 9652kb
input:
100000 2 1 - 3 1 - 4 1 - 5 1 - 6 1 - 7 1 Duan 8 1 - 9 1 - 10 1 - 11 3 - 12 2 - 13 1 - 14 1 - 15 1 - 16 2 - 17 1 Duan 18 3 - 19 1 - 20 1 Duan 21 8 - 22 2 - 23 3 - 24 3 Duan 25 1 - 26 1 - 27 1 - 28 1 - 29 4 - 30 1 - 31 3 - 32 3 - 33 3 - 34 2 - 35 1 - 36 1 Duan 37 1 - 38 3 - 39 2 - 40 4 - 41 2 Duan 42 ...
output:
NO
result:
ok Correct.
Test #27:
score: 0
Accepted
time: 26ms
memory: 11400kb
input:
100000 2 1 Duan 3 1 Duan 4 1 Duan 5 1 Duan 6 1 Duan 7 1 Duan 8 1 Duan 9 1 Duan 10 1 Duan 11 1 Duan 12 1 Duan 13 1 Duan 14 2 Duan 15 1 Duan 16 1 Duan 17 1 Duan 18 2 Duan 19 1 Duan 20 1 - 21 1 Duan 22 1 Duan 23 1 Duan 24 1 Duan 25 1 Duan 26 1 Duan 27 2 Duan 28 1 Duan 29 1 Duan 30 1 - 31 1 Duan 32 1 Du...
output:
NO
result:
ok Correct.
Test #28:
score: 0
Accepted
time: 19ms
memory: 8444kb
input:
100000 2 1 - 3 1 Duan 4 1 - 5 1 - 6 1 - 7 1 Duan 8 1 - 9 1 Duan 10 1 - 11 1 Duan 12 1 Duan 13 1 Duan 14 1 Duan 15 1 Duan 16 1 - 17 1 Duan 18 1 Duan 19 1 Duan 20 1 Duan 21 1 - 22 1 - 23 1 Duan 24 1 - 25 1 Duan 26 1 Duan 27 1 Duan 28 1 Duan 29 1 Duan 30 1 Duan 31 1 Duan 32 1 - 33 1 - 34 1 Duan 35 1 Du...
output:
NO
result:
ok Correct.
Test #29:
score: 0
Accepted
time: 13ms
memory: 7704kb
input:
100000 2 1 Duan 3 1 Duan 4 1 Duan 5 1 Duan 6 1 Duan 7 1 Duan 8 1 - 9 1 Duan 10 1 Duan 11 1 Duan 12 1 - 13 1 Duan 14 1 Duan 15 1 Duan 16 1 Duan 17 1 Duan 18 1 Duan 19 1 Duan 20 1 - 21 1 - 22 1 Duan 23 1 - 24 1 Duan 25 1 Duan 26 1 Duan 27 1 Duan 28 1 Duan 29 1 Duan 30 1 Duan 31 1 Duan 32 1 Duan 33 1 -...
output:
NO
result:
ok Correct.
Test #30:
score: 0
Accepted
time: 17ms
memory: 8884kb
input:
100000 2 1 Duan 3 1 - 4 1 Duan 5 1 Duan 6 1 Duan 7 1 Duan 8 1 Duan 9 1 Duan 10 1 Duan 11 1 Duan 12 1 Duan 13 1 Duan 14 1 Duan 15 1 Duan 16 1 Duan 17 1 Duan 18 1 Duan 19 1 - 20 1 Duan 21 1 Duan 22 1 Duan 23 1 Duan 24 1 Duan 25 1 Duan 26 1 Duan 27 1 Duan 28 1 - 29 1 Duan 30 1 Duan 31 1 Duan 32 1 - 33 ...
output:
NO
result:
ok Correct.
Test #31:
score: 0
Accepted
time: 21ms
memory: 36556kb
input:
100000 2 1 Duan 3 2 - 4 3 Chang 5 4 - 6 5 Duan 7 6 Chang 8 7 - 9 8 - 10 9 Duan 11 10 Chang 12 11 Duan 13 12 Chang 14 13 Duan 15 14 Chang 16 15 - 17 16 - 18 17 - 19 18 Duan 20 19 - 21 20 - 22 21 Chang 23 22 Duan 24 23 Chang 25 24 - 26 25 Duan 27 26 Chang 28 27 Duan 29 28 - 30 29 Chang 31 30 Duan 32 3...
output:
YES 27102 27101 29450 29449 30582 30581 31109 31108 33545 33544 34349 34348 35395 35394 35627 35626 35742 35741 36326 36325 36980 36979 37026 37025 37781 37780 37917 37916 38566 38565 38779 38778 38884 38882 39163 39162 39441 39440 39610 39609 39689 39688 39924 39923 39995 39994 40981 40980 41018 41...
result:
ok Correct.
Test #32:
score: 0
Accepted
time: 18ms
memory: 7704kb
input:
100000 2 1 Duan 3 1 - 4 1 - 5 1 - 6 1 - 7 1 - 8 1 - 9 1 - 10 1 - 11 1 - 12 1 Tong 13 1 - 14 1 - 15 1 - 16 1 Tong 17 1 - 18 1 - 19 1 - 20 1 - 21 1 - 22 1 Tong 23 1 - 24 1 - 25 1 - 26 1 - 27 1 - 28 1 - 29 1 - 30 1 - 31 1 - 32 1 - 33 1 - 34 1 - 35 1 - 36 1 - 37 1 - 38 1 Tong 39 1 - 40 1 - 41 1 - 42 1 -...
output:
YES 83748 84085 84052 84039 84036 84021 83989 83963 83894 83892 83875 83862 83794 83778 84100 83732 83710 83697 83679 83646 83641 83589 83567 83505 83453 83382 83381 83339 84510 84988 84986 84948 84886 84880 84874 84830 84731 84706 84680 84652 84592 84567 83330 84494 84484 84459 84457 84340 84313 84...
result:
ok Correct.
Test #33:
score: 0
Accepted
time: 27ms
memory: 11060kb
input:
93284 2 1 - 3 1 Duan 4 2 - 5 4 - 6 2 - 7 4 Duan 8 1 - 9 4 - 10 4 Duan 11 6 - 12 7 - 13 6 - 14 1 Duan 15 4 - 16 9 - 17 12 - 18 15 - 19 6 Duan 20 1 - 21 15 - 22 2 - 23 5 Duan 24 7 - 25 22 - 26 13 - 27 12 - 28 6 - 29 27 Duan 30 7 Duan 31 9 - 32 14 - 33 3 - 34 21 - 35 18 - 36 35 - 37 7 - 38 17 Duan 39 2...
output:
YES 44871 9427 58881 75107 33984 7193 33178 9737 89725 31043 31602 50618 88133 870 58845 52086 63567 21758 85296 16605 44633 28152 65095 2705 90927 18041 42717 56227 88253 10288 61450 16710 71661 49645 48970 30561 37354 20860 34821 31734 37862 29953 80450 37189 93257 56610 14996 30431 91146 42455 59...
result:
ok Correct.
Test #34:
score: 0
Accepted
time: 32ms
memory: 11520kb
input:
92284 2 1 Duan 3 2 - 4 3 Duan 5 2 Duan 6 3 - 7 4 Duan 8 6 Duan 9 4 Duan 10 6 Duan 11 4 Duan 12 8 Chang 13 1 Duan 14 5 Duan 15 5 - 16 15 Duan 17 15 Duan 18 13 Chang 19 12 Duan 20 4 - 21 1 Duan 22 17 Duan 23 2 Duan 24 14 Duan 25 17 Duan 26 22 Duan 27 4 - 28 26 Duan 29 9 Duan 30 15 Duan 31 3 Duan 32 7 ...
output:
YES 51080 17459 32219 16873 56156 11101 74549 52633 82117 51694 32559 38566 48460 186 41891 25888 84667 83294 87183 52019 88982 77715 78351 13583 87627 83209 46901 62069 86376 8557 3604 986 83765 79770 80461 49864 74127 22996 69795 42259 61472 91303 35154 29187 15829 25303 27245 62442 52319 171 8444...
result:
ok Correct.
Test #35:
score: 0
Accepted
time: 31ms
memory: 10884kb
input:
93444 2 1 - 3 1 Duan 4 1 Duan 5 2 - 6 4 - 7 3 - 8 6 Duan 9 6 Duan 10 9 - 11 2 - 12 1 - 13 11 - 14 5 - 15 14 Duan 16 11 - 17 16 - 18 4 - 19 7 Duan 20 15 - 21 17 - 22 21 - 23 20 - 24 23 Duan 25 7 - 26 14 Duan 27 18 - 28 13 Duan 29 2 Duan 30 19 Duan 31 5 - 32 7 Duan 33 23 Duan 34 17 Duan 35 2 Duan 36 2...
output:
YES 63791 54500 49024 4643 37302 55459 33770 26344 81449 28229 87768 65404 24623 33539 82147 51327 70787 90272 14888 9603 47285 47877 40135 29487 4308 353 72113 34651 58261 41429 64780 22648 81320 68254 57783 50381 85526 25357 76795 43913 34185 41202 41133 46835 54622 10796 76020 140 47575 1923 8801...
result:
ok Correct.
Test #36:
score: 0
Accepted
time: 33ms
memory: 11380kb
input:
98244 2 1 Duan 3 1 Duan 4 3 Duan 5 4 Duan 6 4 Duan 7 4 Duan 8 5 Duan 9 8 Duan 10 5 Duan 11 9 Duan 12 3 Duan 13 11 Tong 14 5 Duan 15 5 Duan 16 12 Duan 17 2 Duan 18 3 Duan 19 4 Duan 20 2 Duan 21 6 Duan 22 21 Duan 23 1 - 24 15 - 25 20 Duan 26 8 Duan 27 13 Duan 28 12 Duan 29 22 Duan 30 24 Duan 31 21 Dua...
output:
YES 33409 16406 15284 30277 35906 6139 58902 93724 47922 18729 24670 20659 47533 41216 84590 48839 87728 4161 95897 74471 23810 3459 29076 9591 34342 9185 80103 95194 87229 22109 28966 14850 15423 8235 42356 13261 78438 9379 89672 35400 67130 33413 91476 9648 73800 23306 79990 3540 87242 877 94629 9...
result:
ok Correct.
Test #37:
score: 0
Accepted
time: 13ms
memory: 5596kb
input:
25284 2 1 Duan 3 2 - 4 3 - 5 3 Duan 6 2 Duan 7 3 Duan 8 1 Duan 9 5 - 10 4 - 11 5 Duan 12 4 Duan 13 1 Duan 14 4 - 15 10 Duan 16 8 - 17 13 - 18 15 - 19 12 - 20 16 Duan 21 6 Duan 22 2 Duan 23 19 - 24 12 - 25 2 - 26 19 Duan 27 5 - 28 4 - 29 9 - 30 12 Duan 31 7 Duan 32 31 - 33 21 - 34 24 Duan 35 28 Duan ...
output:
YES 14929 5340 15736 7415 23406 22917 14380 15197 24417 14590 3602 7880 1894 15884 9136 12672 5678 3206 24111 15621 14368 20232 21718 25101 7241 1931 24489 19471 23289 8812 22451 12521 1629 130 23008 21864 9095 3189 22734 15113 12465 10604 6996 6641 22852 1537 23329 765 20447 16208 18299 2439 13012 ...
result:
ok Correct.
Test #38:
score: 0
Accepted
time: 30ms
memory: 11548kb
input:
93246 2 1 Duan 3 2 Duan 4 3 Duan 5 1 - 6 4 Tong 7 4 Duan 8 4 Duan 9 8 - 10 6 Duan 11 2 Duan 12 1 Duan 13 11 Duan 14 8 Duan 15 1 Duan 16 8 Duan 17 10 Duan 18 3 Duan 19 1 Duan 20 18 Duan 21 10 Duan 22 14 Duan 23 11 Duan 24 19 Duan 25 21 Duan 26 17 Duan 27 24 Duan 28 24 Duan 29 17 Tong 30 23 Duan 31 17...
output:
YES 82440 20027 82065 37790 55902 13555 93214 9444 54322 14967 47686 8102 71322 23936 78461 77717 48337 45254 83570 52000 29015 24317 91719 723 63413 35283 3250 89556 60951 81387 50544 76768 24023 6264 92751 27168 78391 65278 46265 14547 92070 81407 69857 47136 28099 17204 33721 19861 55462 24774 84...
result:
ok Correct.
Test #39:
score: 0
Accepted
time: 35ms
memory: 11692kb
input:
99837 2 1 - 3 1 - 4 3 Duan 5 2 Duan 6 5 Duan 7 3 Duan 8 5 - 9 6 Duan 10 4 - 11 4 - 12 6 Duan 13 8 - 14 7 - 15 10 Duan 16 11 Duan 17 8 Duan 18 6 - 19 13 Duan 20 16 Duan 21 20 - 22 19 Chang 23 4 Duan 24 13 Duan 25 21 - 26 17 Duan 27 7 Duan 28 8 - 29 3 - 30 18 - 31 21 Duan 32 27 Duan 33 21 Duan 34 17 -...
output:
YES 37610 77117 30206 19111 70345 88367 36504 20744 75785 43637 79180 14266 83709 26231 55639 85507 10520 3564 21314 11286 90540 30850 56410 51043 77737 66938 89082 86756 37423 10348 81449 10238 89645 63757 42718 30451 91346 49790 74087 27842 86402 61765 73518 33536 55707 45163 33231 25335 51349 766...
result:
ok Correct.
Test #40:
score: 0
Accepted
time: 33ms
memory: 11512kb
input:
91248 2 1 Duan 3 1 Duan 4 1 Duan 5 2 Duan 6 3 Duan 7 3 Chang 8 2 Duan 9 1 Duan 10 7 Duan 11 10 Duan 12 4 Duan 13 2 Duan 14 11 Duan 15 6 Duan 16 8 Duan 17 7 Duan 18 2 Duan 19 15 Duan 20 4 Duan 21 7 Duan 22 6 Duan 23 6 Duan 24 20 Duan 25 13 Duan 26 22 Duan 27 5 Duan 28 19 Duan 29 14 Duan 30 12 - 31 8 ...
output:
YES 22567 91137 32840 6625 72793 2746 49857 58707 9195 6406 75118 17873 70816 13271 36187 35070 36004 34727 77775 60624 56136 40146 7879 3419 50744 81884 35818 75987 90945 56940 12926 1090 77013 73408 48058 45541 26944 55452 58680 55908 78364 43609 77661 45709 55964 32151 71423 12836 52096 21580 629...
result:
ok Correct.
Test #41:
score: 0
Accepted
time: 30ms
memory: 10944kb
input:
93538 2 1 - 3 2 - 4 2 - 5 3 Duan 6 4 - 7 4 - 8 2 - 9 1 - 10 7 - 11 4 Duan 12 8 - 13 9 - 14 1 Duan 15 7 Duan 16 3 - 17 5 - 18 14 Duan 19 5 - 20 7 - 21 15 Duan 22 9 - 23 8 - 24 16 Duan 25 5 Duan 26 6 Duan 27 10 - 28 7 - 29 21 Duan 30 1 - 31 18 - 32 13 - 33 6 - 34 28 - 35 16 Duan 36 32 Duan 37 22 - 38 ...
output:
YES 43838 19363 42715 63190 20329 10322 70798 78903 45972 14986 62809 83054 52182 1456 62218 19710 85461 84523 52940 12256 31914 7475 39273 86366 61296 21575 78432 12897 67416 23096 81263 61831 53716 686 31961 24734 45084 29776 70937 57302 25231 58268 85989 35275 19663 19412 70970 45326 55647 34007 ...
result:
ok Correct.
Test #42:
score: 0
Accepted
time: 30ms
memory: 11068kb
input:
92384 2 1 Duan 3 2 - 4 3 Duan 5 3 Duan 6 3 - 7 2 Duan 8 1 - 9 7 Duan 10 5 Chang 11 4 - 12 3 Duan 13 7 - 14 9 Duan 15 14 Chang 16 3 Duan 17 6 Duan 18 10 Duan 19 17 Duan 20 10 - 21 2 Duan 22 10 - 23 5 Duan 24 18 - 25 11 - 26 13 Duan 27 12 Duan 28 1 - 29 18 Duan 30 28 Duan 31 28 - 32 16 - 33 27 Duan 34...
output:
YES 40387 40096 83783 43478 3917 3661 50150 89303 18917 15374 34799 48940 81225 61144 63107 81589 29948 20682 14730 1795 23638 13591 84669 2983 38473 33792 33668 26822 91365 72727 58495 52159 54079 10991 69625 73581 31305 43086 48339 39523 88518 14352 91546 65295 89085 34909 34637 3467 74155 17285 2...
result:
ok Correct.
Test #43:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
1
output:
YES
result:
ok Correct.