QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#544068	#1869. Power Station of Art	PhantomThreshold	AC ✓	594ms	119888kb	C++20	1.8kb	2024-09-02 02:33:54	2024-09-02 02:33:54

Judging History

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

[2024-09-02 02:33:54]
评测

测评结果：AC
用时：594ms
内存：119888kb

查看

[2024-09-02 02:33:54]
提交

answer

#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
#define int long long
using namespace std;
using ull=unsigned long long;

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	mt19937_64 rng(41287482);
	
	const int maxw=1e6;
	vector<ull> w(maxw+5);
	for(int i=0;i<=maxw;i++)
		w[i]=rng();
	
	int Tcase; cin>>Tcase;
	while(Tcase--)
	{
		int n,m;
		cin>>n>>m;
		vector<vector<int>> G(n+5);
		for(int i=1;i<=m;i++)
		{
			int u,v;
			cin>>u>>v;
			G[u].push_back(v);
			G[v].push_back(u);
		}
		vector<int> a(n+5),b(n+5);
		string ca,cb;
		for(int i=1;i<=n;i++)cin>>a[i];
		cin>>ca;
		ca=' '+ca;
		for(int i=1;i<=n;i++)cin>>b[i];
		cin>>cb;
		cb=' '+cb;
		vector<int> bel(n+5),good(n+5),col(n+5);
		vector<int> cntr(n+5);
		vector<vector<multiset<int>>> suma(2,vector<multiset<int>>(n+5));
		vector<vector<multiset<int>>> sumb(2,vector<multiset<int>>(n+5));
		function<void(int,int)> dfs=[&](int r,int u)
		{
			bel[u]=r;
			for(auto v:G[u])
			{
				if(not bel[v])
				{
					col[v]=col[u]^1;
					dfs(r,v);
				}
				else if(col[u]==col[v])
					good[r]=0;
			}
		};
		for(int i=1;i<=n;i++)
		{
			if(not bel[i])
			{
				good[i]=1;
				dfs(i,i);
			}
		}
		for(int i=1;i<=n;i++)
		{
			if(good[bel[i]])
			{
				suma[(ca[i]=='R')^col[i]][bel[i]].insert(a[i]);
				sumb[(cb[i]=='R')^col[i]][bel[i]].insert(b[i]);
			}
			else
			{
				if(ca[i]=='R')cntr[bel[i]]^=1;
				if(cb[i]=='R')cntr[bel[i]]^=1;
				suma[0][bel[i]].insert(a[i]);
				sumb[0][bel[i]].insert(b[i]);
			}
		}
		int ok=1;
		for(int i=1;i<=n;i++)
		{
			if(cntr[i]!=0)ok=0;
			if(suma[0][i]!=sumb[0][i] or suma[1][i]!=sumb[1][i])ok=0;
		}
		if(ok)cout<<"YES\n";
		else cout<<"NO\n";
	}
	
	return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 5ms

memory: 11124kb

input:

output:

YES
NO
YES

result:

ok 3 lines

Test #2:

score: 0

Accepted

time: 594ms

memory: 119888kb

input:

25054
5 10
4 5
4 2
4 3
4 1
5 2
5 3
5 1
2 3
2 1
3 1
12 2 9 10 7
RRRBB
10 2 9 7 12
RRBRB
1 0
4
R
4
R
8 4
4 3
1 5
8 5
6 5
7 2 11 10 9 6 3 5
RBRBBRBR
7 2 10 11 6 5 3 9
RBRBBRBR
7 4
7 2
5 1
5 6
5 4
12 5 9 14 5 12 12
RRBRBRR
14 12 9 5 12 12 5
RBBRBRB
10 1
4 6
5 3 2 9 7 3 11 11 6 8
RRRBRRBBBR
5 3 2 3 7 9 1...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
NO
NO
YES
YES
YES
NO
YES
NO
YES
YES
NO
YES
YES
NO
YES
NO
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
NO
NO...

result:

ok 25054 lines