QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#283282	#1869. Power Station of Art	5ab	AC ✓	216ms	24952kb	C++20	2.1kb	2023-12-14 11:49:21	2023-12-14 11:49:22

Judging History

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

[2023-12-14 11:49:22]
评测

测评结果：AC
用时：216ms
内存：24952kb

查看

[2023-12-14 11:49:21]
提交

answer

/* name: G
 * author: 5ab
 * created at: 2023-12-13
 */
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define ssz(x) (int((x).size()))

auto chmax = [](auto& x, auto y) { if (x < y) x = y; };
auto chmin = [](auto& x, auto y) { if (y < x) x = y; };

using ll = long long;
const int max_n = 1e6, max_m = 1e6;

int hd[max_n], des[max_m], nxt[max_m], a1[max_n], a2[max_n], e_cnt = 0;
char s1[max_n + 1], s2[max_n + 1];
int cl[max_n];

void add(int s, int t)
{
	des[e_cnt] = t;
	nxt[e_cnt] = hd[s];
	hd[s] = e_cnt++;
}

vector<pair<int, int>> x1, x2;
int c1[2], c2[2];
bool dfs(int id)
{
	bool ans = 1;
	// cerr << id << " " << s1[id] << " " << s2[id] << " " << cl[id] << endl;
	x1.emplace_back(a1[id], (s1[id] == 'R') ^ cl[id]);
	x2.emplace_back(a2[id], (s2[id] == 'R') ^ cl[id]);
	c1[s1[id] == 'R']++, c2[s2[id] == 'R']++;
	for (int p = hd[id], dst; p != -1; p = nxt[p])
	{
		dst = des[p];
		if (cl[dst] == -1)
		{
			cl[dst] = cl[id] ^ 1;
			ans &= dfs(dst);
		}
		else if (cl[dst] == cl[id])
			ans = 0;
	}
	return ans;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int cas, n, m;
	
	cin >> cas;
	while (cas--)
	{
		cin >> n >> m;
		
		fill(hd, hd + n, -1), e_cnt = 0;
		for (int i = 0, x, y; i < m; i++)
		{
			cin >> x >> y, x--, y--;
			add(x, y), add(y, x);
		}
		for (int i = 0; i < n; i++)
			cin >> a1[i];
		cin >> s1;
		for (int i = 0; i < n; i++)
			cin >> a2[i];
		cin >> s2;
		
		fill(cl, cl + n, -1);
		bool ok = 1;
		for (int i = 0; i < n; i++) if (cl[i] == -1)
		{
			x1.clear(), x2.clear();
			c1[0] = c1[1] = c2[0] = c2[1] = 0;
			cl[i] = 0;
			bool ty = dfs(i);
			sort(all(x1)), sort(all(x2));
			if (ty)
			{
				for (int j = 0; j < ssz(x1); j++)
					ok &= (x1[j] == x2[j]);
			}
			else
			{
				for (int j = 0; j < ssz(x1); j++)
					ok &= (x1[j].first == x2[j].first);
				ok &= (((c1[0] ^ c2[0]) & 1) == 0);
			}
		}
		cout << (ok ? "YES" : "NO") << "\n";
	}
	
	return 0;
}
// started coding at: 12-13 20:16:01

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 15852kb

input:

output:

YES
NO
YES

result:

ok 3 lines

Test #2:

score: 0

Accepted

time: 216ms

memory: 24952kb

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