oj.uz

Submission #585728

# Submission time Handle Problem Language Result Execution time Memory
585728 2022-06-29T09:13:58 Z red24 Experimental Charges (NOI19_charges) C++14
32 / 100
 146 ms 9216 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 py = find_set(y);
	int px = find_set(x);
	for (auto k : chds[py]) 
	{
		col[k] = !col[k];
		chds[px].pb(k);
	}
	chds[py].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 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 9216 KB Output is correct
2 Correct 118 ms 9056 KB Output is correct
3 Correct 122 ms 8920 KB Output is correct
4 Correct 106 ms 9000 KB Output is correct
5 Correct 107 ms 9036 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 9016 KB Output is correct
2 Correct 130 ms 9044 KB Output is correct
3 Correct 133 ms 8992 KB Output is correct
4 Correct 106 ms 8880 KB Output is correct
5 Correct 125 ms 9140 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 9092 KB Output is correct
2 Correct 125 ms 9068 KB Output is correct
3 Incorrect 104 ms 8868 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 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Incorrect 4 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 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 124 ms 9216 KB Output is correct
7 Correct 118 ms 9056 KB Output is correct
8 Correct 122 ms 8920 KB Output is correct
9 Correct 106 ms 9000 KB Output is correct
10 Correct 107 ms 9036 KB Output is correct
11 Correct 123 ms 9016 KB Output is correct
12 Correct 130 ms 9044 KB Output is correct
13 Correct 133 ms 8992 KB Output is correct
14 Correct 106 ms 8880 KB Output is correct
15 Correct 125 ms 9140 KB Output is correct
16 Correct 146 ms 9092 KB Output is correct
17 Correct 125 ms 9068 KB Output is correct
18 Incorrect 104 ms 8868 KB Output isn't correct
19 Halted 0 ms 0 KB -