oj.uz

Submission #333053

# Submission time Handle Problem Language Result Execution time Memory
333053 2020-12-04T11:31:38 Z banterbry Experimental Charges (NOI19_charges) C++17
46 / 100
 1000 ms 8200 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
typedef pair<int,int> pi;

#ifdef LOCAL
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 69
#endif
template <typename Arg>
void __f(string name, Arg arg) {
	cerr << name << " = " << arg << endl;
}
template <typename Head, typename... Tail>
void __f(string names, Head head, Tail... tail) {
	string cur = "";
	for (auto ch: names){if(ch==','){break;}else{cur+=ch;}}
	string nxt = names.substr(cur.size()+2);
	cerr << cur << " = " << head << ", ";
	__f(nxt, tail...);
}

const int mxn = 1e5 + 5;
int n, q, par[mxn], sz[mxn];
bool charge[mxn];
vector<int> adj[mxn];

int root(int x) {
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
}
bool same(int x, int y) {return root(x) == root(y);}
void unite(int x, int y) {
    x = root(x), y = root(y);
    if (x == y) return;
    par[x] = y; 
    sz[y] += sz[x];
}

void dfs(int x, int p) {
	charge[x] = !charge[x];
	for (auto i: adj[x]) {
		if (i == p) continue;
		dfs(i, x);
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) par[i] = i, sz[i] = 1;
	while (q--) {
		char op; int a, b;
		cin >> op >> a >> b;
		if (op == 'Q') {
			if (!same(a, b)) cout << '?';
			else cout << (charge[a] == charge[b] ? 'R' : 'A');
			cout << '\n';
		} else {
			if (op == 'R') {
				if (charge[a] != charge[b]) {
					if (sz[a] > sz[b]) swap(a, b);
					dfs(a, a);
				}
			} else {	
				if (charge[a] == charge[b]) {
					if (sz[a] > sz[b]) swap(a, b);
					dfs(a, a);
				}
			}
			if (!same(a, b)) {
				unite(a, b);
				adj[a].pb(b);
				adj[b].pb(a);
			}
		}
	}
	return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 5904 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 7404 KB Output is correct
2 Correct 42 ms 7148 KB Output is correct
3 Correct 45 ms 7404 KB Output is correct
4 Correct 60 ms 8172 KB Output is correct
5 Correct 60 ms 7936 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 8200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
25.0 / 25.0

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

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2796 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Execution timed out 1092 ms 5904 KB Time limit exceeded
7 Halted 0 ms 0 KB -