oj.uz

Submission #587349

# Submission time Handle Problem Language Result Execution time Memory
587349 2022-07-01T16:56:08 Z red24 Experimental Charges (NOI19_charges) C++14
100 / 100
 145 ms 11004 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)
{
	for (auto k : chds[y]) 
	{
		col[k] = !col[k];
	}
}

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);
	
	for (auto k : chds[y])
	{
		chds[x].pb(k);
	}
	chds[y].clear();

	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 3 ms 4948 KB Output is correct
3 Correct 4 ms 5008 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5012 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 10088 KB Output is correct
2 Correct 106 ms 10028 KB Output is correct
3 Correct 139 ms 10096 KB Output is correct
4 Correct 131 ms 10108 KB Output is correct
5 Correct 123 ms 10056 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 10628 KB Output is correct
2 Correct 135 ms 10684 KB Output is correct
3 Correct 143 ms 10484 KB Output is correct
4 Correct 118 ms 10828 KB Output is correct
5 Correct 128 ms 11004 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 10508 KB Output is correct
2 Correct 124 ms 10356 KB Output is correct
3 Correct 114 ms 10388 KB Output is correct
4 Correct 128 ms 10800 KB Output is correct
5 Correct 128 ms 10716 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5008 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5012 KB Output is correct
6 Correct 4 ms 5016 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 4 ms 5024 KB Output is correct
10 Correct 5 ms 4948 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5008 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5012 KB Output is correct
6 Correct 126 ms 10088 KB Output is correct
7 Correct 106 ms 10028 KB Output is correct
8 Correct 139 ms 10096 KB Output is correct
9 Correct 131 ms 10108 KB Output is correct
10 Correct 123 ms 10056 KB Output is correct
11 Correct 123 ms 10628 KB Output is correct
12 Correct 135 ms 10684 KB Output is correct
13 Correct 143 ms 10484 KB Output is correct
14 Correct 118 ms 10828 KB Output is correct
15 Correct 128 ms 11004 KB Output is correct
16 Correct 132 ms 10508 KB Output is correct
17 Correct 124 ms 10356 KB Output is correct
18 Correct 114 ms 10388 KB Output is correct
19 Correct 128 ms 10800 KB Output is correct
20 Correct 128 ms 10716 KB Output is correct
21 Correct 4 ms 5016 KB Output is correct
22 Correct 4 ms 4948 KB Output is correct
23 Correct 4 ms 5076 KB Output is correct
24 Correct 4 ms 5024 KB Output is correct
25 Correct 5 ms 4948 KB Output is correct
26 Correct 145 ms 10540 KB Output is correct
27 Correct 139 ms 10568 KB Output is correct
28 Correct 105 ms 10452 KB Output is correct
29 Correct 108 ms 10588 KB Output is correct
30 Correct 127 ms 10572 KB Output is correct