oj.uz

Submission #550444

# Submission time Handle Problem Language Result Execution time Memory
550444 2022-04-18T08:19:09 Z LittleCube Inside information (BOI21_servers) C++14
50 / 100
 259 ms 31712 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int N, K, a[240005], b[240005], dsu[120005], rk[120005], aca[240005], acb[240005], ans[240005], cur[120005];
vector<int> Q[120005];
map<int, int> mp[240005];
vector<pii> undo;
char t[240005];

int find(int k)
{
	return dsu[k] == k ? k : find(dsu[k]);
}

void merge(int x, int y, int tag = 0)
{
	int rx = find(x), ry = find(y);
	if(rx == ry)
		return;
	if(rk[rx] <= rk[ry])
	{
		dsu[rx] = ry;
		rk[ry] += rk[rx];
		if(tag)
		{	
			Q[ry].emplace_back(tag);
			aca[tag] = rx;
			acb[tag] = ry;
		}
		else 
			undo.emplace_back(pii(rx, ry));
	}
	else
	{
		dsu[ry] = rx;
		rk[rx] += rk[ry];
		if(tag)
		{	
			Q[rx].emplace_back(tag);
			aca[tag] = rx;
			acb[tag] = ry;
		}
		else 
			undo.emplace_back(pii(ry, rx));

	}
}

void rollback(int t)
{
	while(undo.size() > t)
	{
		auto [x, y] = undo.back();
		undo.pop_back();
		dsu[x] = x;
		rk[y] -= rk[x];
	}
}

void solve(int k)
{
	int sz = undo.size();
	while(!Q[k].empty())
	{
		int i = Q[k].back();
		Q[k].pop_back();
		if(t[i] == 'S')
		{
			merge(a[i], b[i]);
			solve(aca[i]);
			solve(acb[i]);
			break;	
		}
		else if(t[i] == 'Q')
			ans[i] = (find(a[i]) == find(b[i]));
	}
	rollback(sz);
}

signed main()
{
	cin >> N >> K;
	K += N - 1;
	for(int i = 1; i <= K; i++)
	{
		cin >> t[i];
		if(t[i] == 'C')
			cin >> a[i];
		else
			cin >> a[i] >> b[i];
	}	
	for(int i = 1; i <= N; i++)
		dsu[i] = i, cur[i] = rk[i] = 1;
	for(int i = K; i >= 1; i--)
	{
		if(t[i] == 'S')
		{	
			merge(a[i], b[i], i);
			cur[a[i]] += cur[b[i]];
			cur[b[i]] = cur[a[i]];
		}
		else if(t[i] == 'C')
			ans[i] = cur[a[i]];
		else
		{
			int r = find(a[i]);
			Q[r].emplace_back(i);
		}
	}
	int r = find(1);
	for(int i = 1; i <= N; i++)
		dsu[i] = i, rk[i] = 1;
	solve(r);
	for(int i = 1; i <= K; i++)
		if(t[i] == 'C')
			cout << ans[i] << '\n';
		else if(t[i] == 'Q')
			cout << (ans[i] ? "yes\n" : "no\n");
}

Compilation message

servers.cpp: In function 'void rollback(int)':
servers.cpp:56:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |  while(undo.size() > t)
      |        ~~~~~~~~~~~~^~~
servers.cpp:58:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |   auto [x, y] = undo.back();
      |        ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 18248 KB Output is correct
2 Correct 85 ms 19556 KB Output is correct
3 Correct 81 ms 19788 KB Output is correct
4 Correct 89 ms 19648 KB Output is correct
5 Correct 87 ms 18756 KB Output is correct
6 Correct 86 ms 19208 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 18248 KB Output is correct
2 Correct 85 ms 19556 KB Output is correct
3 Correct 81 ms 19788 KB Output is correct
4 Correct 89 ms 19648 KB Output is correct
5 Correct 87 ms 18756 KB Output is correct
6 Correct 86 ms 19208 KB Output is correct
7 Incorrect 59 ms 18104 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 64 ms 18152 KB Output is correct
2 Correct 196 ms 31240 KB Output is correct
3 Correct 197 ms 31192 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 64 ms 18152 KB Output is correct
2 Correct 196 ms 31240 KB Output is correct
3 Correct 197 ms 31192 KB Output is correct
4 Incorrect 60 ms 18192 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 18340 KB Output is correct
2 Correct 237 ms 27392 KB Output is correct
3 Correct 202 ms 27340 KB Output is correct
4 Correct 190 ms 31672 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 18340 KB Output is correct
2 Correct 237 ms 27392 KB Output is correct
3 Correct 202 ms 27340 KB Output is correct
4 Correct 190 ms 31672 KB Output is correct
5 Incorrect 76 ms 18292 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 18180 KB Output is correct
2 Correct 190 ms 29516 KB Output is correct
3 Correct 229 ms 27396 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 18180 KB Output is correct
2 Correct 190 ms 29516 KB Output is correct
3 Correct 229 ms 27396 KB Output is correct
4 Incorrect 60 ms 18292 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 18380 KB Output is correct
2 Correct 221 ms 27300 KB Output is correct
3 Correct 200 ms 27320 KB Output is correct
4 Correct 183 ms 31604 KB Output is correct
5 Correct 67 ms 18284 KB Output is correct
6 Correct 193 ms 29528 KB Output is correct
7 Correct 215 ms 27432 KB Output is correct
8 Correct 256 ms 26704 KB Output is correct
9 Correct 209 ms 27212 KB Output is correct
10 Correct 198 ms 31472 KB Output is correct
11 Correct 189 ms 31292 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 18380 KB Output is correct
2 Correct 221 ms 27300 KB Output is correct
3 Correct 200 ms 27320 KB Output is correct
4 Correct 183 ms 31604 KB Output is correct
5 Correct 67 ms 18284 KB Output is correct
6 Correct 193 ms 29528 KB Output is correct
7 Correct 215 ms 27432 KB Output is correct
8 Correct 256 ms 26704 KB Output is correct
9 Correct 209 ms 27212 KB Output is correct
10 Correct 198 ms 31472 KB Output is correct
11 Correct 189 ms 31292 KB Output is correct
12 Incorrect 64 ms 18208 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 18148 KB Output is correct
2 Correct 93 ms 19516 KB Output is correct
3 Correct 82 ms 19812 KB Output is correct
4 Correct 84 ms 19572 KB Output is correct
5 Correct 85 ms 18760 KB Output is correct
6 Correct 84 ms 19228 KB Output is correct
7 Correct 59 ms 18236 KB Output is correct
8 Correct 189 ms 31160 KB Output is correct
9 Correct 195 ms 31304 KB Output is correct
10 Correct 58 ms 18356 KB Output is correct
11 Correct 193 ms 27328 KB Output is correct
12 Correct 207 ms 27456 KB Output is correct
13 Correct 184 ms 31712 KB Output is correct
14 Correct 59 ms 18256 KB Output is correct
15 Correct 182 ms 29584 KB Output is correct
16 Correct 206 ms 27376 KB Output is correct
17 Correct 209 ms 26652 KB Output is correct
18 Correct 259 ms 27096 KB Output is correct
19 Correct 183 ms 31440 KB Output is correct
20 Correct 198 ms 31292 KB Output is correct
21 Correct 209 ms 30176 KB Output is correct
22 Correct 197 ms 30888 KB Output is correct
23 Correct 219 ms 27464 KB Output is correct
24 Correct 210 ms 27596 KB Output is correct
25 Correct 206 ms 29384 KB Output is correct
26 Correct 200 ms 30108 KB Output is correct
27 Correct 179 ms 30184 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 18148 KB Output is correct
2 Correct 93 ms 19516 KB Output is correct
3 Correct 82 ms 19812 KB Output is correct
4 Correct 84 ms 19572 KB Output is correct
5 Correct 85 ms 18760 KB Output is correct
6 Correct 84 ms 19228 KB Output is correct
7 Correct 59 ms 18236 KB Output is correct
8 Correct 189 ms 31160 KB Output is correct
9 Correct 195 ms 31304 KB Output is correct
10 Correct 58 ms 18356 KB Output is correct
11 Correct 193 ms 27328 KB Output is correct
12 Correct 207 ms 27456 KB Output is correct
13 Correct 184 ms 31712 KB Output is correct
14 Correct 59 ms 18256 KB Output is correct
15 Correct 182 ms 29584 KB Output is correct
16 Correct 206 ms 27376 KB Output is correct
17 Correct 209 ms 26652 KB Output is correct
18 Correct 259 ms 27096 KB Output is correct
19 Correct 183 ms 31440 KB Output is correct
20 Correct 198 ms 31292 KB Output is correct
21 Correct 209 ms 30176 KB Output is correct
22 Correct 197 ms 30888 KB Output is correct
23 Correct 219 ms 27464 KB Output is correct
24 Correct 210 ms 27596 KB Output is correct
25 Correct 206 ms 29384 KB Output is correct
26 Correct 200 ms 30108 KB Output is correct
27 Correct 179 ms 30184 KB Output is correct
28 Incorrect 62 ms 18092 KB Extra information in the output file
29 Halted 0 ms 0 KB -