QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#379182#6396. Puzzle: KusabiAINgrayWA 40ms11796kbC++235.6kb2024-04-06 16:31:142024-04-06 16:31:15

Judging History

你现在查看的是最新测评结果

  • [2024-04-06 16:31:15]
  • 评测
  • 测评结果:WA
  • 用时:40ms
  • 内存:11796kb
  • [2024-04-06 16:31:14]
  • 提交

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.