QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#380926#6396. Puzzle: KusabiinvadedWA 25ms45416kbC++173.9kb2024-04-07 15:06:142024-04-07 15:06:14

Judging History

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

  • [2024-04-07 15:06:14]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:45416kb
  • [2024-04-07 15:06:14]
  • 提交

answer

#include<bits/stdc++.h>
#ifndef xxx
#define dbg(...) ;
#endif
using namespace std;
template<class T> ostream &operator<<(ostream &o, const vector <T> &v) { bool f=false; for(T i:v) { f?o<<' ':o; o<<(i); f=true; } return o; }
template<class T> void sort(T &v) { std::sort(v.begin(), v.end()); }
template<class T, class C> void sort(T &v, C c) { std::sort(v.begin(), v.end(), c); }
template<class T> void reverse(T &v) { std::reverse(v.begin(), v.end()); }
template<class T> bool is_sorted(T &v) { return std::is_sorted(v.begin(), v.end()); }
template<class T> inline void left_shift(T st, T ed, int shift) { std::rotate(st, st+shift, ed); }
template<class T> inline void right_shift(T st, T ed, int shift) { std::rotate(st, ed-shift, ed); }
template<class T> inline void _min(T &x, const T &y) { x>y?x=y:x; }
template<class T> inline void _max(T &x, const T &y) { x<y?x=y:x; }
istream &operator>>(istream &i, __int128_t &x) { x=0; short f=1; char c=0; while(!isdigit(c)) { if(c=='-')f=-1; c=i.get(); } while(isdigit(c))x=x*10+c-'0', c=i.get(); x*=f; return i; }
ostream &operator<<(ostream &o, __int128_t x) { if(x==0) { o<<0; return o; } bool f=false; string s; if(x<0)f=true, x=-x; while(x)s+=x%10+'0', x/=10; reverse(s); if(f)o<<'-'; o<<s; return o; }
mt19937 mt(time(0));
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
constexpr int maxn=2e5+5;
constexpr int mod=1e9+7;
constexpr int inf=0x3f3f3f3f;
constexpr ll INF=0x3f3f3f3f3f3f3f3fll;
constexpr double pi=acos(-1.0);
constexpr double eps=1e-9;
struct node
{
	int id, type, dep;
	node() :id(0), type(0), dep(0) {}
	node(int id, int type, int dep)
	{
		this->id=id;
		this->type=type;
		this->dep=dep;
	}
}nd[maxn];
vector<int>G[maxn];
vector<int>layer[maxn];
// (dep,id)
set<pii>chang[maxn], duan[maxn], tong[maxn];
void dfs(int u)
{
	//dbg(u);
	layer[nd[u].dep].push_back(u);
	for(int v:G[u])
	{
		dfs(v);
	}
}
int main()//MARK: main
{
#ifndef xxx
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#endif
	cout<<fixed<<setprecision(10);
	int n;
	cin>>n;
	for(int i=1; i<=n-1; i++)
	{
		int id, type, dep;
		int p;
		string s;
		cin>>id>>p>>s;
		if(s[0]=='C')type=1;
		else if(s[0]=='D')type=2;
		else if(s[0]=='T')type=3;
		else type=0;
		dep=nd[p].dep+1;
		nd[id]=node(id, type, dep);
		G[p].push_back(id);
	}
	dfs(1);
	vector<pii>ans;
	auto getans=[&]()->bool
	{
		for(int d=n; d>=0; d--)
		{
			if(layer[d].empty())continue;
			dbg(d);
			for(int u:layer[d])
			{
				auto [id, type, dep]=nd[u];
				auto &C=chang[u];
				auto &D=duan[u];
				auto &T=tong[u];
				for(int v:G[u])
				{
					C.insert(chang[v].begin(), chang[v].end());
					D.insert(duan[v].begin(), duan[v].end());
					T.insert(tong[v].begin(), tong[v].end());
				}
				if(type==1)C.insert({dep, u});
				else if(type==2)D.insert({dep, u});
				else if(type==3)T.insert({dep, u});
				dbg(u, type, C.size(), D.size(), T.size());
				while(!C.empty())
				{
					auto c=C.begin();
					auto it=D.lower_bound({c->first, 0});
					if(it!=D.begin())
					{
						it--;
						dbg(c->first, it->first);
						ans.push_back({c->second, it->second});
						D.erase(it);
						C.erase(c);
					}
					else
					{
						break;
					}
				}
				while(!T.empty())
				{
					auto t=T.begin();
					T.erase(t);
					auto it=T.lower_bound({t->first, 0});
					if(it!=T.end()&&it->first==t->first)
					{
						T.erase(it);
						ans.push_back({t->second, it->second});
					}
					else
					{
						T.insert(make_pair(t->first, t->second));
						break;
					}
				}
				if(C.size()+D.size()+T.size()>1)
				{
					return false;
				}
			}
		}
		return chang[1].empty()&&duan[1].empty()&&tong[1].empty();
	};
	if(getans())
	{
		cout<<"YES"<<'\n';
		for(auto [u, v]:ans)
		{
			cout<<u<<' '<<v<<'\n';
		}
	}
	else
	{
		cout<<"NO"<<'\n';
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 43620kb

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: 0ms
memory: 43492kb

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: 8ms
memory: 43536kb

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 25ms
memory: 45416kb

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.