oj.uz

Submission #441507

# Submission time Handle Problem Language Result Execution time Memory
441507 2021-07-05T09:38:26 Z 8e7 Inside information (BOI21_servers) C++14
52.5 / 100
 3500 ms 49100 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 {
			cnt = 0;
			lim = cur;
			solve(i.a, 0, 0);
			cout << cnt << "\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 41 ms 5788 KB Output is correct
2 Correct 60 ms 6736 KB Output is correct
3 Correct 48 ms 6980 KB Output is correct
4 Correct 74 ms 6872 KB Output is correct
5 Correct 59 ms 7164 KB Output is correct
6 Correct 47 ms 6884 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5788 KB Output is correct
2 Correct 60 ms 6736 KB Output is correct
3 Correct 48 ms 6980 KB Output is correct
4 Correct 74 ms 6872 KB Output is correct
5 Correct 59 ms 7164 KB Output is correct
6 Correct 47 ms 6884 KB Output is correct
7 Correct 43 ms 5636 KB Output is correct
8 Correct 55 ms 7496 KB Output is correct
9 Correct 241 ms 7580 KB Output is correct
10 Correct 61 ms 7592 KB Output is correct
11 Correct 56 ms 7752 KB Output is correct
12 Correct 895 ms 7752 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5844 KB Output is correct
2 Correct 181 ms 39836 KB Output is correct
3 Correct 170 ms 39780 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5844 KB Output is correct
2 Correct 181 ms 39836 KB Output is correct
3 Correct 170 ms 39780 KB Output is correct
4 Correct 38 ms 5672 KB Output is correct
5 Execution timed out 3581 ms 42312 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5816 KB Output is correct
2 Correct 152 ms 46856 KB Output is correct
3 Correct 153 ms 46848 KB Output is correct
4 Correct 214 ms 46700 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5816 KB Output is correct
2 Correct 152 ms 46856 KB Output is correct
3 Correct 153 ms 46848 KB Output is correct
4 Correct 214 ms 46700 KB Output is correct
5 Correct 38 ms 5684 KB Output is correct
6 Correct 156 ms 48928 KB Output is correct
7 Execution timed out 3594 ms 49100 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5776 KB Output is correct
2 Correct 185 ms 39820 KB Output is correct
3 Correct 156 ms 40304 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5776 KB Output is correct
2 Correct 185 ms 39820 KB Output is correct
3 Correct 156 ms 40304 KB Output is correct
4 Correct 40 ms 5664 KB Output is correct
5 Execution timed out 3597 ms 42112 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5816 KB Output is correct
2 Correct 158 ms 46832 KB Output is correct
3 Correct 152 ms 46752 KB Output is correct
4 Correct 217 ms 46708 KB Output is correct
5 Correct 41 ms 5748 KB Output is correct
6 Correct 184 ms 39800 KB Output is correct
7 Correct 154 ms 40256 KB Output is correct
8 Correct 275 ms 40672 KB Output is correct
9 Correct 192 ms 40752 KB Output is correct
10 Correct 227 ms 44520 KB Output is correct
11 Correct 364 ms 43896 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5816 KB Output is correct
2 Correct 158 ms 46832 KB Output is correct
3 Correct 152 ms 46752 KB Output is correct
4 Correct 217 ms 46708 KB Output is correct
5 Correct 41 ms 5748 KB Output is correct
6 Correct 184 ms 39800 KB Output is correct
7 Correct 154 ms 40256 KB Output is correct
8 Correct 275 ms 40672 KB Output is correct
9 Correct 192 ms 40752 KB Output is correct
10 Correct 227 ms 44520 KB Output is correct
11 Correct 364 ms 43896 KB Output is correct
12 Correct 40 ms 5604 KB Output is correct
13 Correct 158 ms 49008 KB Output is correct
14 Execution timed out 3570 ms 48864 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5812 KB Output is correct
2 Correct 59 ms 6728 KB Output is correct
3 Correct 48 ms 6932 KB Output is correct
4 Correct 73 ms 6984 KB Output is correct
5 Correct 60 ms 7072 KB Output is correct
6 Correct 46 ms 6804 KB Output is correct
7 Correct 37 ms 5812 KB Output is correct
8 Correct 172 ms 39764 KB Output is correct
9 Correct 168 ms 39816 KB Output is correct
10 Correct 38 ms 5816 KB Output is correct
11 Correct 156 ms 46492 KB Output is correct
12 Correct 155 ms 46368 KB Output is correct
13 Correct 245 ms 46444 KB Output is correct
14 Correct 39 ms 5784 KB Output is correct
15 Correct 196 ms 39860 KB Output is correct
16 Correct 171 ms 40308 KB Output is correct
17 Correct 273 ms 40660 KB Output is correct
18 Correct 217 ms 40672 KB Output is correct
19 Correct 228 ms 44528 KB Output is correct
20 Correct 357 ms 44052 KB Output is correct
21 Correct 204 ms 39748 KB Output is correct
22 Correct 212 ms 39960 KB Output is correct
23 Correct 221 ms 40324 KB Output is correct
24 Correct 208 ms 40256 KB Output is correct
25 Correct 211 ms 41456 KB Output is correct
26 Correct 184 ms 39688 KB Output is correct
27 Correct 145 ms 39664 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5812 KB Output is correct
2 Correct 59 ms 6728 KB Output is correct
3 Correct 48 ms 6932 KB Output is correct
4 Correct 73 ms 6984 KB Output is correct
5 Correct 60 ms 7072 KB Output is correct
6 Correct 46 ms 6804 KB Output is correct
7 Correct 37 ms 5812 KB Output is correct
8 Correct 172 ms 39764 KB Output is correct
9 Correct 168 ms 39816 KB Output is correct
10 Correct 38 ms 5816 KB Output is correct
11 Correct 156 ms 46492 KB Output is correct
12 Correct 155 ms 46368 KB Output is correct
13 Correct 245 ms 46444 KB Output is correct
14 Correct 39 ms 5784 KB Output is correct
15 Correct 196 ms 39860 KB Output is correct
16 Correct 171 ms 40308 KB Output is correct
17 Correct 273 ms 40660 KB Output is correct
18 Correct 217 ms 40672 KB Output is correct
19 Correct 228 ms 44528 KB Output is correct
20 Correct 357 ms 44052 KB Output is correct
21 Correct 204 ms 39748 KB Output is correct
22 Correct 212 ms 39960 KB Output is correct
23 Correct 221 ms 40324 KB Output is correct
24 Correct 208 ms 40256 KB Output is correct
25 Correct 211 ms 41456 KB Output is correct
26 Correct 184 ms 39688 KB Output is correct
27 Correct 145 ms 39664 KB Output is correct
28 Correct 47 ms 5600 KB Output is correct
29 Correct 57 ms 7424 KB Output is correct
30 Correct 266 ms 7620 KB Output is correct
31 Correct 61 ms 7496 KB Output is correct
32 Correct 53 ms 7736 KB Output is correct
33 Correct 916 ms 7704 KB Output is correct
34 Correct 38 ms 6324 KB Output is correct
35 Execution timed out 3558 ms 42084 KB Time limit exceeded
36 Halted 0 ms 0 KB -