oj.uz

Submission #585724

# Submission time Handle Problem Language Result Execution time Memory
585724 2022-06-29T09:11:17 Z red24 Experimental Charges (NOI19_charges) C++14
32 / 100
 151 ms 10196 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];
		chds[x].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 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 5012 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 9164 KB Output is correct
2 Correct 93 ms 9468 KB Output is correct
3 Correct 151 ms 9152 KB Output is correct
4 Correct 127 ms 9264 KB Output is correct
5 Correct 97 ms 9276 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 9172 KB Output is correct
2 Correct 119 ms 9216 KB Output is correct
3 Correct 148 ms 9260 KB Output is correct
4 Correct 132 ms 9144 KB Output is correct
5 Correct 137 ms 9404 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 9164 KB Output is correct
2 Correct 131 ms 10196 KB Output is correct
3 Incorrect 124 ms 10052 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 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 5012 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Incorrect 3 ms 5076 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 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 5012 KB Output is correct
6 Correct 99 ms 9164 KB Output is correct
7 Correct 93 ms 9468 KB Output is correct
8 Correct 151 ms 9152 KB Output is correct
9 Correct 127 ms 9264 KB Output is correct
10 Correct 97 ms 9276 KB Output is correct
11 Correct 125 ms 9172 KB Output is correct
12 Correct 119 ms 9216 KB Output is correct
13 Correct 148 ms 9260 KB Output is correct
14 Correct 132 ms 9144 KB Output is correct
15 Correct 137 ms 9404 KB Output is correct
16 Correct 121 ms 9164 KB Output is correct
17 Correct 131 ms 10196 KB Output is correct
18 Incorrect 124 ms 10052 KB Output isn't correct
19 Halted 0 ms 0 KB -