QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#544069	#1869. Power Station of Art	PhantomThreshold	AC ✓	606ms	112300kb	C++20	1.7kb	2024-09-02 02:34:45	2024-09-02 02:34:46

Judging History

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

[2024-09-02 02:34:46]
评测

测评结果：AC
用时：606ms
内存：112300kb

查看

[2024-09-02 02:34:45]
提交

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);
	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: 1ms

memory: 3628kb

input:

output:

YES
NO
YES

result:

ok 3 lines

Test #2:

score: 0

Accepted

time: 606ms

memory: 112300kb

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