oj.uz

Submission #584518

# Submission time Handle Problem Language Result Execution time Memory
584518 2022-06-27T13:46:25 Z red24 Experimental Charges (NOI19_charges) C++14
18 / 100
 145 ms 10740 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 unite(int x, int y, bool rel_charge)
{
	x = find_set(x); y = find_set(y);
	if (x == y) return;

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

	if ((rel_charge == 1 && col[x] == col[y]) || (rel_charge == 0 && col[x] != col[y]))
	{
		for(auto k : chds[y]) col[k] = !col[k];
	}
	
	for (auto k : chds[y]) chds[x].pb(k);
	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 (par[a] != par[b]) {cout << "?"; nl; continue;}
			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 3 ms 4948 KB Output is correct
4 Correct 2 ms 5016 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 109 ms 10064 KB Output is correct
2 Correct 122 ms 10096 KB Output is correct
3 Correct 128 ms 10036 KB Output is correct
4 Correct 122 ms 10156 KB Output is correct
5 Correct 116 ms 10140 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 10740 KB Output is correct
2 Correct 121 ms 10612 KB Output is correct
3 Incorrect 145 ms 10488 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 131 ms 10492 KB Output isn't correct
2 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 3 ms 4948 KB Output is correct
4 Correct 2 ms 5016 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Incorrect 4 ms 5076 KB Output isn't correct
7 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 3 ms 4948 KB Output is correct
4 Correct 2 ms 5016 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 109 ms 10064 KB Output is correct
7 Correct 122 ms 10096 KB Output is correct
8 Correct 128 ms 10036 KB Output is correct
9 Correct 122 ms 10156 KB Output is correct
10 Correct 116 ms 10140 KB Output is correct
11 Correct 124 ms 10740 KB Output is correct
12 Correct 121 ms 10612 KB Output is correct
13 Incorrect 145 ms 10488 KB Output isn't correct
14 Halted 0 ms 0 KB -