oj.uz

Submission #585727

# Submission time Handle Problem Language Result Execution time Memory
585727 2022-06-29T09:12:47 Z red24 Experimental Charges (NOI19_charges) C++14
32 / 100
 144 ms 9144 KB 
#include <bits/stdc++.h>
using namespace std;

#define vi vector<int> 
#define vvi vector<vector<int>>
#define pi pair<int>
#define ppi pair<pair<int>>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define OK cout << "OK" << '\n'
#define qi queue<int>
#define sti stack<int>
#define si stack<int>
#define yes cout << "Yes" << '\n'
#define no cout << "No" << '\n'
#define pb push_back
#define eb emplace_back
#define vpi vector<pair<int, int>>
#define ll long long
#define nl cout << '\n'
#define ok cout << "OK" << '\n'

void printvec(vi v)
{
	rep(i, 1, v.size()-1) cout << v[i] << ' '; nl;
}

// PROGRAM
const int MOD = (int)1e9 + 7;
const int mx = 2e5;
int par[mx];
int siz[mx];
bool col[mx];
vi chds[mx];

void make_set(int x)
{
	par[x] = x;
	siz[x] = 1;
	col[x] = 1;
	chds[x].pb(x);
}

int find_set(int x)
{
	if (par[x] == x) return x;
	else return par[x] = find_set(par[x]);
}

void update(int x, int y)
{
	int px = find_set(x);
	for (auto k : chds[y]) 
	{
		col[k] = !col[k];
		chds[px].pb(k);
	}
	chds[y].clear();
}

void unite(int x, int y, bool charge)
{
	bool ox = col[x];
	bool oy = col[y];
	x = find_set(x); y = find_set(y);
	if (x == y) return;

	if (siz[x] < siz[y]) swap(x, y);

	if ((charge == 1 && ox == oy) || (charge == 0 && ox != oy)) update(x, y);
	
	siz[x] += siz[y];
	par[y] = x;
}

void solve()
{
	// CHECK IF PROGRAM HAS TESTCASES
	int n, q; cin >> n >> q;
	rep(i, 1, n) make_set(i);
	while (q--)
	{
		char t; cin >> t;
		int a, b; cin >> a >> b;

		// PART ONE
		if (t == 'A')
		{
			unite(a, b, 1);
		}
		else if (t == 'R')
		{
			unite(a, b, 0);
		}

		else
		{
			if (find_set(a) != find_set(b)) cout << "?" << '\n';
			else if (col[a] == col[b]) cout << "R" << '\n';
			else cout << "A" << '\n';
		}
	}

}

int main()
{
	int T = 1;
	// cin >> T;
	while (T--) solve();
}

Compilation message

charges.cpp: In function 'void printvec(std::vector<int>)':
charges.cpp:8:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define rep(i, a, b) for (int i = a; i <= b; i++)
......
   24 |  rep(i, 1, v.size()-1) cout << v[i] << ' '; nl;
      |      ~~~~~~~~~~~~~~~~                   
charges.cpp:24:2: note: in expansion of macro 'rep'
   24 |  rep(i, 1, v.size()-1) cout << v[i] << ' '; nl;
      |  ^~~

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 9088 KB Output is correct
2 Correct 94 ms 9008 KB Output is correct
3 Correct 127 ms 8896 KB Output is correct
4 Correct 111 ms 9000 KB Output is correct
5 Correct 114 ms 9144 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 9036 KB Output is correct
2 Correct 122 ms 9108 KB Output is correct
3 Correct 131 ms 8968 KB Output is correct
4 Correct 100 ms 8908 KB Output is correct
5 Correct 144 ms 9056 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 9100 KB Output is correct
2 Correct 135 ms 8976 KB Output is correct
3 Incorrect 111 ms 8876 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 4 ms 5044 KB Output is correct
7 Correct 4 ms 5072 KB Output is correct
8 Incorrect 3 ms 4948 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 99 ms 9088 KB Output is correct
7 Correct 94 ms 9008 KB Output is correct
8 Correct 127 ms 8896 KB Output is correct
9 Correct 111 ms 9000 KB Output is correct
10 Correct 114 ms 9144 KB Output is correct
11 Correct 134 ms 9036 KB Output is correct
12 Correct 122 ms 9108 KB Output is correct
13 Correct 131 ms 8968 KB Output is correct
14 Correct 100 ms 8908 KB Output is correct
15 Correct 144 ms 9056 KB Output is correct
16 Correct 117 ms 9100 KB Output is correct
17 Correct 135 ms 8976 KB Output is correct
18 Incorrect 111 ms 8876 KB Output isn't correct
19 Halted 0 ms 0 KB -