oj.uz

Submission #585712

# Submission time Handle Problem Language Result Execution time Memory
585712 2022-06-29T08:57:12 Z red24 Experimental Charges (NOI19_charges) C++14
32 / 100
 138 ms 10988 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);
	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 << "?"; 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 5008 KB Output is correct
4 Correct 3 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 98 ms 9212 KB Output is correct
2 Correct 115 ms 10048 KB Output is correct
3 Correct 128 ms 10032 KB Output is correct
4 Correct 107 ms 10140 KB Output is correct
5 Correct 114 ms 10060 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 9532 KB Output is correct
2 Correct 123 ms 10560 KB Output is correct
3 Correct 136 ms 10572 KB Output is correct
4 Correct 113 ms 10764 KB Output is correct
5 Correct 138 ms 10988 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 131 ms 9216 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 5008 KB Output is correct
4 Correct 3 ms 4948 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 5008 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 98 ms 9212 KB Output is correct
7 Correct 115 ms 10048 KB Output is correct
8 Correct 128 ms 10032 KB Output is correct
9 Correct 107 ms 10140 KB Output is correct
10 Correct 114 ms 10060 KB Output is correct
11 Correct 131 ms 9532 KB Output is correct
12 Correct 123 ms 10560 KB Output is correct
13 Correct 136 ms 10572 KB Output is correct
14 Correct 113 ms 10764 KB Output is correct
15 Correct 138 ms 10988 KB Output is correct
16 Incorrect 131 ms 9216 KB Output isn't correct
17 Halted 0 ms 0 KB -