QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#417750	#1869. Power Station of Art	Kevin5307	AC ✓	971ms	47444kb	C++23	2.5kb	2024-05-22 21:38:11	2024-05-22 21:38:11

Judging History

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

[2024-05-22 21:38:11]
评测

测评结果：AC
用时：971ms
内存：47444kb

查看

[2024-05-22 21:38:11]
提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
vector<int> G[1001000];
int n,m,vis[1001000],color[1001000];
string color1,color2;
int number1[1001000],number2[1001000];
bool bipar;
map<int,int> Cnt[2][3][2];
set<int> st;
void dfs(int u,int c=1)
{
	st.insert(number1[u]);
	vis[u]=1;
	Cnt[0][color[u]][color1[u-1]=='B'][number1[u]]++;
	Cnt[1][color[u]][color2[u-1]=='B'][number2[u]]++;
	color[u]=c;
	Cnt[0][color[u]][color1[u-1]=='B'][number1[u]]++;
	Cnt[1][color[u]][color2[u-1]=='B'][number2[u]]++;
	for(auto v:G[u])
		if(!vis[v])
			dfs(v,3-c);
		else if(color[v]==c) bipar=false;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			vis[i]=color[i]=0;
			G[i].clear();
		}
		for(int i=1;i<=m;i++)
		{
			int u,v;
			cin>>u>>v;
			G[u].pb(v);
			G[v].pb(u);
		}
		for(int i=1;i<=n;i++)
			cin>>number1[i];
		cin>>color1;
		for(int i=1;i<=n;i++)
			cin>>number2[i];
		cin>>color2;
		bool ok=true;
		for(int i=1;i<=n;i++)
			if(!vis[i])
			{
				st.clear();
				bipar=true;
				for(int a=0;a<2;a++)
					for(int b=0;b<3;b++)
						for(int c=0;c<2;c++)
							Cnt[a][b][c].clear();
				dfs(i);
				if(bipar)
				{
					for(auto x:st)
					{
						if(Cnt[0][0][0][x]+Cnt[0][0][1][x]!=Cnt[1][0][0][x]+Cnt[1][0][1][x])
							ok=false;
						if(Cnt[0][1][0][x]+Cnt[0][2][1][x]!=Cnt[1][1][0][x]+Cnt[1][2][1][x])
							ok=false;
						if(Cnt[0][1][1][x]+Cnt[0][2][0][x]!=Cnt[1][1][1][x]+Cnt[1][2][0][x])
							ok=false;
					}
				}
				else
				{
					int ch=0;
					for(auto x:st)
					{
						if(Cnt[0][0][0][x]+Cnt[0][0][1][x]!=Cnt[1][0][0][x]+Cnt[1][0][1][x])
							ok=false;
						if((Cnt[0][0][0][x]-Cnt[1][0][0][x])%2)
							ch^=1;
					}
					if(ch)
						ok=false;
				}
			}
		if(ok)
			cout<<"YES\n";
		else
			cout<<"NO\n";
	}
	return 0;
}

源文件, 语言: C++23

詳細信息

Test #1:

score: 100

Accepted

time: 3ms

memory: 11728kb

input:

output:

YES
NO
YES

result:

ok 3 lines

Test #2:

score: 0

Accepted

time: 971ms

memory: 47444kb

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