oj.uz

Submission #441523

# Submission time Handle Problem Language Result Execution time Memory
441523 2021-07-05T09:57:10 Z 8e7 Inside information (BOI21_servers) C++14
55 / 100
 1507 ms 49072 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 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});
			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 {
			int ans = 1;
			int low = i.a, up = n + 1;	
			while (low < up - 1) {
				int mid = (low + up) / 2;
				pii p = mono(i.a, mid);
				if (p.ff <= cur && p.ss) low = mid;
				else up = mid;
			}
			ans += low - i.a;
			
			low = 0, up = i.a;
			while (low < up - 1) {
				int mid = (low + up) / 2;
				pii p = mono(i.a, mid);
				if (p.ff <= cur && p.ss) up = mid;
				else low = mid;
			}
			ans += i.a - up;
			cout << ans << "\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

7 7
S 4 5
S 2 3
S 5 6
S 6 7
S 3 4
S 1 2
C 1
C 2
C 3
C 4
C 5
C 6
C 7
   */

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 6080 KB Output is correct
2 Correct 60 ms 7080 KB Output is correct
3 Correct 50 ms 7184 KB Output is correct
4 Correct 73 ms 7236 KB Output is correct
5 Correct 60 ms 7484 KB Output is correct
6 Correct 47 ms 7104 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 6080 KB Output is correct
2 Correct 60 ms 7080 KB Output is correct
3 Correct 50 ms 7184 KB Output is correct
4 Correct 73 ms 7236 KB Output is correct
5 Correct 60 ms 7484 KB Output is correct
6 Correct 47 ms 7104 KB Output is correct
7 Incorrect 41 ms 6040 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 38 ms 6172 KB Output is correct
2 Correct 175 ms 40072 KB Output is correct
3 Correct 172 ms 40172 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 6172 KB Output is correct
2 Correct 175 ms 40072 KB Output is correct
3 Correct 172 ms 40172 KB Output is correct
4 Incorrect 39 ms 6028 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 39 ms 6072 KB Output is correct
2 Correct 161 ms 46924 KB Output is correct
3 Correct 167 ms 46796 KB Output is correct
4 Correct 222 ms 46828 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 6072 KB Output is correct
2 Correct 161 ms 46924 KB Output is correct
3 Correct 167 ms 46796 KB Output is correct
4 Correct 222 ms 46828 KB Output is correct
5 Correct 40 ms 5960 KB Output is correct
6 Correct 855 ms 48736 KB Output is correct
7 Correct 986 ms 49072 KB Output is correct
8 Correct 1486 ms 48604 KB Output is correct
9 Correct 1469 ms 48684 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 6052 KB Output is correct
2 Correct 187 ms 40084 KB Output is correct
3 Correct 165 ms 40576 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 6052 KB Output is correct
2 Correct 187 ms 40084 KB Output is correct
3 Correct 165 ms 40576 KB Output is correct
4 Incorrect 40 ms 5980 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 41 ms 6040 KB Output is correct
2 Correct 164 ms 46768 KB Output is correct
3 Correct 180 ms 46768 KB Output is correct
4 Correct 219 ms 46784 KB Output is correct
5 Correct 40 ms 6072 KB Output is correct
6 Correct 196 ms 40160 KB Output is correct
7 Correct 166 ms 40652 KB Output is correct
8 Correct 312 ms 41072 KB Output is correct
9 Correct 190 ms 41032 KB Output is correct
10 Correct 229 ms 44832 KB Output is correct
11 Correct 383 ms 44368 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 6040 KB Output is correct
2 Correct 164 ms 46768 KB Output is correct
3 Correct 180 ms 46768 KB Output is correct
4 Correct 219 ms 46784 KB Output is correct
5 Correct 40 ms 6072 KB Output is correct
6 Correct 196 ms 40160 KB Output is correct
7 Correct 166 ms 40652 KB Output is correct
8 Correct 312 ms 41072 KB Output is correct
9 Correct 190 ms 41032 KB Output is correct
10 Correct 229 ms 44832 KB Output is correct
11 Correct 383 ms 44368 KB Output is correct
12 Correct 40 ms 6084 KB Output is correct
13 Correct 883 ms 48732 KB Output is correct
14 Correct 1006 ms 48928 KB Output is correct
15 Correct 1507 ms 48672 KB Output is correct
16 Correct 1486 ms 48492 KB Output is correct
17 Incorrect 40 ms 6200 KB Extra information in the output file
18 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 6132 KB Output is correct
2 Correct 60 ms 7028 KB Output is correct
3 Correct 49 ms 7224 KB Output is correct
4 Correct 75 ms 7352 KB Output is correct
5 Correct 61 ms 7404 KB Output is correct
6 Correct 47 ms 7132 KB Output is correct
7 Correct 38 ms 6088 KB Output is correct
8 Correct 172 ms 40100 KB Output is correct
9 Correct 174 ms 40196 KB Output is correct
10 Correct 41 ms 6100 KB Output is correct
11 Correct 149 ms 46700 KB Output is correct
12 Correct 156 ms 46704 KB Output is correct
13 Correct 233 ms 46824 KB Output is correct
14 Correct 40 ms 6084 KB Output is correct
15 Correct 192 ms 40060 KB Output is correct
16 Correct 157 ms 40684 KB Output is correct
17 Correct 294 ms 40944 KB Output is correct
18 Correct 191 ms 40964 KB Output is correct
19 Correct 218 ms 44940 KB Output is correct
20 Correct 358 ms 44272 KB Output is correct
21 Correct 189 ms 40212 KB Output is correct
22 Correct 200 ms 40288 KB Output is correct
23 Correct 202 ms 40592 KB Output is correct
24 Correct 198 ms 40648 KB Output is correct
25 Correct 180 ms 41784 KB Output is correct
26 Correct 148 ms 39924 KB Output is correct
27 Correct 144 ms 40092 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 6132 KB Output is correct
2 Correct 60 ms 7028 KB Output is correct
3 Correct 49 ms 7224 KB Output is correct
4 Correct 75 ms 7352 KB Output is correct
5 Correct 61 ms 7404 KB Output is correct
6 Correct 47 ms 7132 KB Output is correct
7 Correct 38 ms 6088 KB Output is correct
8 Correct 172 ms 40100 KB Output is correct
9 Correct 174 ms 40196 KB Output is correct
10 Correct 41 ms 6100 KB Output is correct
11 Correct 149 ms 46700 KB Output is correct
12 Correct 156 ms 46704 KB Output is correct
13 Correct 233 ms 46824 KB Output is correct
14 Correct 40 ms 6084 KB Output is correct
15 Correct 192 ms 40060 KB Output is correct
16 Correct 157 ms 40684 KB Output is correct
17 Correct 294 ms 40944 KB Output is correct
18 Correct 191 ms 40964 KB Output is correct
19 Correct 218 ms 44940 KB Output is correct
20 Correct 358 ms 44272 KB Output is correct
21 Correct 189 ms 40212 KB Output is correct
22 Correct 200 ms 40288 KB Output is correct
23 Correct 202 ms 40592 KB Output is correct
24 Correct 198 ms 40648 KB Output is correct
25 Correct 180 ms 41784 KB Output is correct
26 Correct 148 ms 39924 KB Output is correct
27 Correct 144 ms 40092 KB Output is correct
28 Incorrect 42 ms 6084 KB Extra information in the output file
29 Halted 0 ms 0 KB -