oj.uz

Submission #522263

# Submission time Handle Problem Language Result Execution time Memory
522263 2022-02-04T11:11:57 Z blue Experimental Charges (NOI19_charges) C++17
100 / 100
 26 ms 3356 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int mx = 100'000;
using vi = vector<int>;
using pii = pair<int, int>;

struct disjoint_set
{
	vector<pii> parent = vector<pii>(1+mx);
	vi subtree = vi(1+mx, 1);
	vi flip = vi(1+mx, 0);

	disjoint_set()
	{
		for(int i = 1; i <= mx; i++) parent[i] = {i, 0};
	}

	pii root(int u)
	{
		if(parent[u].first == u) return {u, 0};
		else
		{
			pii pr = root(parent[u].first);
			pr.second ^= parent[u].second;
			parent[u] = pr;
			return pr;
		}
	}

	void join(int u, int v, bool b)
	{
		pii up = root(u), vp = root(v);
		if(up.first == vp.first) return;

		if(subtree[up.first] < subtree[vp.first]) swap(up, vp);
		subtree[up.first] += subtree[vp.first];
		parent[vp.first] = {up.first, b ^ up.second ^ vp.second};
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, Q;
	cin >> N >> Q;

	disjoint_set DS;

	for(int q = 1; q <= Q; q++)
	{
		char T;
		int A, B;
		cin >> T >> A >> B;

		if(T == 'A') DS.join(A, B, 1);
		else if(T == 'R') DS.join(A, B, 0);
		else 
		{
			pii AP = DS.root(A), BP = DS.root(B);
			if(AP.first != BP.first) cout << "?\n";
			else if(AP.second == BP.second) cout << "R\n";
			else cout << "A\n";
		}
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 1 ms 1860 KB Output is correct
4 Correct 1 ms 1868 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2740 KB Output is correct
2 Correct 20 ms 2764 KB Output is correct
3 Correct 19 ms 2804 KB Output is correct
4 Correct 18 ms 2884 KB Output is correct
5 Correct 17 ms 2792 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3216 KB Output is correct
2 Correct 20 ms 3224 KB Output is correct
3 Correct 26 ms 3356 KB Output is correct
4 Correct 21 ms 3288 KB Output is correct
5 Correct 22 ms 3304 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3140 KB Output is correct
2 Correct 21 ms 3244 KB Output is correct
3 Correct 19 ms 3152 KB Output is correct
4 Correct 25 ms 3276 KB Output is correct
5 Correct 26 ms 3160 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 1 ms 1860 KB Output is correct
4 Correct 1 ms 1868 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 1 ms 1852 KB Output is correct
7 Correct 1 ms 1868 KB Output is correct
8 Correct 1 ms 1868 KB Output is correct
9 Correct 2 ms 1852 KB Output is correct
10 Correct 1 ms 1868 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 1 ms 1860 KB Output is correct
4 Correct 1 ms 1868 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 21 ms 2740 KB Output is correct
7 Correct 20 ms 2764 KB Output is correct
8 Correct 19 ms 2804 KB Output is correct
9 Correct 18 ms 2884 KB Output is correct
10 Correct 17 ms 2792 KB Output is correct
11 Correct 22 ms 3216 KB Output is correct
12 Correct 20 ms 3224 KB Output is correct
13 Correct 26 ms 3356 KB Output is correct
14 Correct 21 ms 3288 KB Output is correct
15 Correct 22 ms 3304 KB Output is correct
16 Correct 20 ms 3140 KB Output is correct
17 Correct 21 ms 3244 KB Output is correct
18 Correct 19 ms 3152 KB Output is correct
19 Correct 25 ms 3276 KB Output is correct
20 Correct 26 ms 3160 KB Output is correct
21 Correct 1 ms 1852 KB Output is correct
22 Correct 1 ms 1868 KB Output is correct
23 Correct 1 ms 1868 KB Output is correct
24 Correct 2 ms 1852 KB Output is correct
25 Correct 1 ms 1868 KB Output is correct
26 Correct 20 ms 3208 KB Output is correct
27 Correct 20 ms 3268 KB Output is correct
28 Correct 21 ms 3152 KB Output is correct
29 Correct 20 ms 3148 KB Output is correct
30 Correct 20 ms 3172 KB Output is correct