oj.uz

Submission #441514

# Submission time Handle Problem Language Result Execution time Memory
441514 2021-07-05T09:44:50 Z 8e7 Inside information (BOI21_servers) C++14
52.5 / 100
 392 ms 46576 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <set>
//#include <ext/pb_ds/assoc_contatiner.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template<class T, class ... U> void debug(T a, U ... b) { cout << a << " ";debug(b...);}
template<class T> void pary (T l, T r) {
	while (l != r) cout << (*l) << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 120005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct query{
	int ti, a, b;
	query() {ti = 0, a = 0, b = 0;}
	query(int x, int y, int z) {ti = x, a = y, b = z;}
};
vector<query> que;
int anc[17][maxn], ma[17][maxn], mi[17][maxn], dep[maxn];
bool inc[17][maxn], decr[17][maxn];

vector<pii> adj[maxn];

void dfs(int n, int par, int d) {
	anc[0][n] = par;
	dep[n] = d;
	inc[0][n] = decr[0][n] = 1;
	for (auto v:adj[n]) {
		if (v.ff != par) {
			ma[0][v.ff] = mi[0][v.ff] = v.ss;
			dfs(v.ff, n, d + 1);
		}
	}
}
pair<int, bool> mono(int a, int b) {
	bool sw = 0, ic = 1, dc = 1;
	int big = 0, small = 1<<20;
	if (dep[a] < dep[b]) sw = 1, swap(a, b);
	int hdif = dep[a] - dep[b], cnt = 0;
	while (hdif) {
		if (hdif & 1) {
			ic &= inc[cnt][a] && ma[0][a] > big;
			dc &= decr[cnt][a] && ma[0][a] < small;	
			big = max(big, ma[cnt][a]), small = min(small, mi[cnt][a]);
			a = anc[cnt][a];
		}
		hdif >>= 1, cnt++;
	}
	return {big, sw ? dc : ic};
}
pair<int, bool> lca(int a, int b) {
	bool sw = 0;
	if (dep[a] < dep[b]) sw = 1, swap(a, b);
	int hdif = dep[a] - dep[b], cnt = 0;
	while (hdif) {
		if (hdif & 1) {
			a = anc[cnt][a];
		}
		hdif >>= 1, cnt++;
	}
	if (a == b) return {a, true};
	for (int i = 16;i >= 0;i--) {
		if (anc[i][a] != anc[i][b]) {
			a = anc[i][a], b = anc[i][b];
		}
	}
	bool val = ma[0][a] < ma[0][b];
	return {anc[0][a], val ^ sw};
}
/*
int cnt = 0, lim = 0;
void solve(int n, int par, int cur) {
	cnt++;
	for (auto v:adj[n]) {
		if (v.ff != par && v.ss > cur && v.ss <= lim) {
			solve(v.ff, n, v.ss);
		}
	}
}
*/
int ti[maxn];
int main() {
	io
	int n, k;
	cin >> n >> k;
	int cur = 1;
	for (int i = 0;i < n + k - 1;i++) {
		char type;
		cin >> type;
		if (type == 'S') {
			int a, b;
			cin >> a >> b;
			adj[a].push_back({b, cur});
			adj[b].push_back({a, cur});
			ti[a] = ti[b] = cur;
			cur++;
			que.push_back(query(0, a, b));
		} else if (type == 'Q') {
			int a, b;
			cin >> a >> b;
			que.push_back(query(1, b, a));
		} else {
			int d;
			cin >> d;
			que.push_back(query(2, d, 0));
		}
	}
	dfs(1, 0, 1);
	//pary(ma[0] + 1, ma[0] + n + 1);
	for (int i = 1;i < 17;i++) {
		for (int j = 1;j <= n;j++) {
			anc[i][j] = anc[i - 1][anc[i - 1][j]];
			ma[i][j] = max(ma[i - 1][j], ma[i - 1][anc[i - 1][j]]);
			mi[i][j] = min(mi[i - 1][j], mi[i - 1][anc[i - 1][j]]);
			inc[i][j] = inc[i - 1][j] && inc[i - 1][anc[i - 1][j]] && ma[i - 1][j] < ma[0][anc[i - 1][j]];
			decr[i][j] = decr[i - 1][j] && decr[i - 1][anc[i - 1][j]] && mi[i - 1][j] > ma[0][anc[i - 1][j]];
			//debug(i, j, ma[i][j], mi[i][j]);
		}
	}
	cur = 0;
	for (auto i:que) {
		if (i.ti == 1) {
			pii p1 = lca(i.a, i.b);
			//debug(p1.ff, p1.ss);
			pii p2 = mono(i.a, p1.ff), p3 = mono(p1.ff, i.b);
			//debug(p2.ff, p2.ss, p3.ff, p3.ss);
			int big = max(p2.ff, p3.ff);
			bool ans = (big <= cur) && p2.ss && p3.ss && p1.ss;
			cout << (ans ? "yes" : "no") << "\n";	
		} else if (i.ti == 0) {
			cur++;
		} else {
			if (i.a == 1) cout << cur + 1 << "\n";
			else {
				cout << (1 + max(0, cur - ti[i.a] + 1)) << "\n";
			}
		}
	}
}
/*
6 9
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
C 1
C 2
C 3
C 4
C 5
C 6
   */

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5352 KB Output is correct
2 Correct 60 ms 6364 KB Output is correct
3 Correct 49 ms 6596 KB Output is correct
4 Correct 72 ms 6468 KB Output is correct
5 Correct 60 ms 6676 KB Output is correct
6 Correct 47 ms 6536 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5352 KB Output is correct
2 Correct 60 ms 6364 KB Output is correct
3 Correct 49 ms 6596 KB Output is correct
4 Correct 72 ms 6468 KB Output is correct
5 Correct 60 ms 6676 KB Output is correct
6 Correct 47 ms 6536 KB Output is correct
7 Incorrect 42 ms 5392 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 47 ms 5468 KB Output is correct
2 Correct 190 ms 39852 KB Output is correct
3 Correct 191 ms 39936 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 5468 KB Output is correct
2 Correct 190 ms 39852 KB Output is correct
3 Correct 191 ms 39936 KB Output is correct
4 Correct 37 ms 5424 KB Output is correct
5 Correct 206 ms 40128 KB Output is correct
6 Correct 99 ms 41884 KB Output is correct
7 Correct 103 ms 42028 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5424 KB Output is correct
2 Correct 160 ms 46552 KB Output is correct
3 Correct 153 ms 46444 KB Output is correct
4 Correct 217 ms 46492 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5424 KB Output is correct
2 Correct 160 ms 46552 KB Output is correct
3 Correct 153 ms 46444 KB Output is correct
4 Correct 217 ms 46492 KB Output is correct
5 Incorrect 38 ms 5416 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 39 ms 5408 KB Output is correct
2 Correct 183 ms 39896 KB Output is correct
3 Correct 164 ms 40428 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5408 KB Output is correct
2 Correct 183 ms 39896 KB Output is correct
3 Correct 164 ms 40428 KB Output is correct
4 Incorrect 38 ms 5396 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 39 ms 5388 KB Output is correct
2 Correct 167 ms 46500 KB Output is correct
3 Correct 150 ms 46516 KB Output is correct
4 Correct 219 ms 46432 KB Output is correct
5 Correct 39 ms 5388 KB Output is correct
6 Correct 186 ms 39920 KB Output is correct
7 Correct 156 ms 40444 KB Output is correct
8 Correct 284 ms 40688 KB Output is correct
9 Correct 190 ms 40832 KB Output is correct
10 Correct 237 ms 44620 KB Output is correct
11 Correct 392 ms 43984 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5388 KB Output is correct
2 Correct 167 ms 46500 KB Output is correct
3 Correct 150 ms 46516 KB Output is correct
4 Correct 219 ms 46432 KB Output is correct
5 Correct 39 ms 5388 KB Output is correct
6 Correct 186 ms 39920 KB Output is correct
7 Correct 156 ms 40444 KB Output is correct
8 Correct 284 ms 40688 KB Output is correct
9 Correct 190 ms 40832 KB Output is correct
10 Correct 237 ms 44620 KB Output is correct
11 Correct 392 ms 43984 KB Output is correct
12 Incorrect 38 ms 5452 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 43 ms 5428 KB Output is correct
2 Correct 59 ms 6384 KB Output is correct
3 Correct 52 ms 6616 KB Output is correct
4 Correct 74 ms 6524 KB Output is correct
5 Correct 60 ms 6772 KB Output is correct
6 Correct 47 ms 6492 KB Output is correct
7 Correct 39 ms 5392 KB Output is correct
8 Correct 177 ms 39836 KB Output is correct
9 Correct 171 ms 39884 KB Output is correct
10 Correct 39 ms 5380 KB Output is correct
11 Correct 155 ms 46444 KB Output is correct
12 Correct 150 ms 46424 KB Output is correct
13 Correct 231 ms 46576 KB Output is correct
14 Correct 43 ms 5424 KB Output is correct
15 Correct 185 ms 39920 KB Output is correct
16 Correct 158 ms 40384 KB Output is correct
17 Correct 311 ms 40680 KB Output is correct
18 Correct 189 ms 40744 KB Output is correct
19 Correct 221 ms 44556 KB Output is correct
20 Correct 371 ms 44040 KB Output is correct
21 Correct 184 ms 39904 KB Output is correct
22 Correct 185 ms 39960 KB Output is correct
23 Correct 202 ms 40444 KB Output is correct
24 Correct 197 ms 40412 KB Output is correct
25 Correct 195 ms 41708 KB Output is correct
26 Correct 161 ms 39844 KB Output is correct
27 Correct 156 ms 39792 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 5428 KB Output is correct
2 Correct 59 ms 6384 KB Output is correct
3 Correct 52 ms 6616 KB Output is correct
4 Correct 74 ms 6524 KB Output is correct
5 Correct 60 ms 6772 KB Output is correct
6 Correct 47 ms 6492 KB Output is correct
7 Correct 39 ms 5392 KB Output is correct
8 Correct 177 ms 39836 KB Output is correct
9 Correct 171 ms 39884 KB Output is correct
10 Correct 39 ms 5380 KB Output is correct
11 Correct 155 ms 46444 KB Output is correct
12 Correct 150 ms 46424 KB Output is correct
13 Correct 231 ms 46576 KB Output is correct
14 Correct 43 ms 5424 KB Output is correct
15 Correct 185 ms 39920 KB Output is correct
16 Correct 158 ms 40384 KB Output is correct
17 Correct 311 ms 40680 KB Output is correct
18 Correct 189 ms 40744 KB Output is correct
19 Correct 221 ms 44556 KB Output is correct
20 Correct 371 ms 44040 KB Output is correct
21 Correct 184 ms 39904 KB Output is correct
22 Correct 185 ms 39960 KB Output is correct
23 Correct 202 ms 40444 KB Output is correct
24 Correct 197 ms 40412 KB Output is correct
25 Correct 195 ms 41708 KB Output is correct
26 Correct 161 ms 39844 KB Output is correct
27 Correct 156 ms 39792 KB Output is correct
28 Incorrect 42 ms 5444 KB Extra information in the output file
29 Halted 0 ms 0 KB -