oj.uz

Submission #574133

# Submission time Handle Problem Language Result Execution time Memory
574133 2022-06-08T02:44:12 Z amunduzbaev Inside information (BOI21_servers) C++17
52.5 / 100
 3500 ms 44076 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array

const int N = 2e5 + 5;
vector<ar<int, 2>> edges[N];
int par[N][20], ed[N], lift[N][20];
int tin[N], tout[N], t, d[N];

void dfs(int u){
	tin[u] = ++t;
	lift[u][0] = (ed[u] > ed[par[u][0]]);
	for(int j=1;j<20;j++){
		par[u][j] = par[par[u][j-1]][j-1];
		lift[u][j] = lift[u][j-1] + lift[par[u][j-1]][j-1];
	}
	
	for(auto x : edges[u]){
		if(x[0] == par[u][0]) continue;
		par[x[0]][0] = u, ed[x[0]] = x[1];
		d[x[0]] = d[u] + 1;
		dfs(x[0]);
	}
	tout[u] = t;
}

bool is(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }

int check(int a, int b, int t){
	if(a == b) return true;
	//~ cout<<a<<" "<<b<<" "<<is(a, b)<<" "<<is(b, a)<<"\n";
	if(is(a, b)){
		int tot = 0;
		for(int j=19;~j;j--){
			if(!is(par[b][j], a)){
				tot += lift[b][j];
				b = par[b][j];
			}
		}
		return (!tot && ed[b] <= t);
	}
	
	if(is(b, a)){
		swap(a, b);
		int tot = 0, o = b;
		for(int j=19;~j;j--){
			if(!is(par[b][j], a)){
				tot += lift[b][j];
				b = par[b][j];
			}
		}
		//~ cout<<tot<<" "<<d[o] - d[b]<<" "<<ed[o]<<"\n";
		return (tot == d[o] - d[b] && ed[o] <= t);
	}
	
	int t1 = 0, t2 = 0, o = a;
	for(int j=19;~j;j--){
		if(!is(par[b][j], a)){
			t1 += lift[b][j];
			b = par[b][j];
		}
		
		if(!is(par[a][j], b)){
			t2 += lift[a][j];
			a = par[a][j];
		}
	}
	//~ cout<<a<<" "<<b<<"\n";
	//~ cout<<t1<<" "<<t2<<" "<<d[a] - d[o]<<" "<<ed[a]<<" "<<ed[b]<<" "<<ed[o]<<"\n";
	return (t1 == 0 && t2 == d[o] - d[a] && ed[a] > ed[b] && ed[o] <= t);
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	vector<ar<int, 3>> q;
	for(int i=1;i<n + m;i++){
		char c; cin>>c;
		if(c == 'S'){
			int a, b; cin>>a>>b;
			edges[a].push_back({b, i});
			edges[b].push_back({a, i});
		} if(c == 'Q') {
			int a, b; cin>>a>>b;
			q.push_back({a, b, i});
		} if(c == 'C'){
			int v; cin>>v;
			q.push_back({-1, v, i});
		}
	}
	
	par[1][0] = 1;
	dfs(1);
	int cnt = 0;
	function<void(int, int, int, int)> dfs = [&](int u, int t, int p, int ed){
		cnt++;
		for(auto x : edges[u]){
			if(x[0] == p || x[1] > t || x[1] <= ed) continue;
			dfs(x[0], t, u, x[1]);
		}
	};
	
	for(auto [a, b, t] : q){
		if(~a){
			if(check(a, b, t)) cout<<"yes\n";
			else cout<<"no\n";
		} else { cnt = 0;
			dfs(b, t, b, 0);
			cout<<cnt<<"\n";
		}
	}
}

/*

6 3
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5

5 1
S 5 4
S 4 1
S 1 2
S 2 3
Q 3 5

*/

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 7828 KB Output is correct
2 Correct 41 ms 8980 KB Output is correct
3 Correct 41 ms 9100 KB Output is correct
4 Correct 56 ms 9268 KB Output is correct
5 Correct 58 ms 9392 KB Output is correct
6 Correct 39 ms 9100 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 7828 KB Output is correct
2 Correct 41 ms 8980 KB Output is correct
3 Correct 41 ms 9100 KB Output is correct
4 Correct 56 ms 9268 KB Output is correct
5 Correct 58 ms 9392 KB Output is correct
6 Correct 39 ms 9100 KB Output is correct
7 Correct 31 ms 7832 KB Output is correct
8 Correct 41 ms 8664 KB Output is correct
9 Correct 292 ms 8904 KB Output is correct
10 Correct 47 ms 8804 KB Output is correct
11 Correct 42 ms 9092 KB Output is correct
12 Correct 1137 ms 8884 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 7872 KB Output is correct
2 Correct 121 ms 35056 KB Output is correct
3 Correct 119 ms 35004 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 7872 KB Output is correct
2 Correct 121 ms 35056 KB Output is correct
3 Correct 119 ms 35004 KB Output is correct
4 Correct 32 ms 7852 KB Output is correct
5 Execution timed out 3543 ms 35012 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7740 KB Output is correct
2 Correct 144 ms 43964 KB Output is correct
3 Correct 159 ms 44076 KB Output is correct
4 Correct 150 ms 44044 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7740 KB Output is correct
2 Correct 144 ms 43964 KB Output is correct
3 Correct 159 ms 44076 KB Output is correct
4 Correct 150 ms 44044 KB Output is correct
5 Correct 29 ms 7824 KB Output is correct
6 Correct 162 ms 43488 KB Output is correct
7 Execution timed out 3579 ms 43632 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7808 KB Output is correct
2 Correct 120 ms 35416 KB Output is correct
3 Correct 126 ms 35964 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7808 KB Output is correct
2 Correct 120 ms 35416 KB Output is correct
3 Correct 126 ms 35964 KB Output is correct
4 Correct 34 ms 7744 KB Output is correct
5 Execution timed out 3573 ms 35000 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 7752 KB Output is correct
2 Correct 134 ms 43964 KB Output is correct
3 Correct 136 ms 43980 KB Output is correct
4 Correct 153 ms 43908 KB Output is correct
5 Correct 31 ms 7788 KB Output is correct
6 Correct 121 ms 35372 KB Output is correct
7 Correct 129 ms 35876 KB Output is correct
8 Correct 160 ms 36356 KB Output is correct
9 Correct 158 ms 36500 KB Output is correct
10 Correct 172 ms 40924 KB Output is correct
11 Correct 233 ms 40172 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 7752 KB Output is correct
2 Correct 134 ms 43964 KB Output is correct
3 Correct 136 ms 43980 KB Output is correct
4 Correct 153 ms 43908 KB Output is correct
5 Correct 31 ms 7788 KB Output is correct
6 Correct 121 ms 35372 KB Output is correct
7 Correct 129 ms 35876 KB Output is correct
8 Correct 160 ms 36356 KB Output is correct
9 Correct 158 ms 36500 KB Output is correct
10 Correct 172 ms 40924 KB Output is correct
11 Correct 233 ms 40172 KB Output is correct
12 Correct 30 ms 7708 KB Output is correct
13 Correct 145 ms 43504 KB Output is correct
14 Execution timed out 3555 ms 43572 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7832 KB Output is correct
2 Correct 42 ms 9036 KB Output is correct
3 Correct 42 ms 9156 KB Output is correct
4 Correct 55 ms 9120 KB Output is correct
5 Correct 44 ms 9452 KB Output is correct
6 Correct 37 ms 9040 KB Output is correct
7 Correct 30 ms 7844 KB Output is correct
8 Correct 111 ms 35052 KB Output is correct
9 Correct 132 ms 35152 KB Output is correct
10 Correct 29 ms 7744 KB Output is correct
11 Correct 140 ms 44068 KB Output is correct
12 Correct 139 ms 44004 KB Output is correct
13 Correct 161 ms 43960 KB Output is correct
14 Correct 37 ms 7820 KB Output is correct
15 Correct 115 ms 35452 KB Output is correct
16 Correct 123 ms 35920 KB Output is correct
17 Correct 155 ms 36368 KB Output is correct
18 Correct 154 ms 36412 KB Output is correct
19 Correct 175 ms 40936 KB Output is correct
20 Correct 207 ms 40232 KB Output is correct
21 Correct 126 ms 35536 KB Output is correct
22 Correct 127 ms 35692 KB Output is correct
23 Correct 134 ms 35796 KB Output is correct
24 Correct 158 ms 35980 KB Output is correct
25 Correct 162 ms 37704 KB Output is correct
26 Correct 129 ms 35392 KB Output is correct
27 Correct 126 ms 35500 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7832 KB Output is correct
2 Correct 42 ms 9036 KB Output is correct
3 Correct 42 ms 9156 KB Output is correct
4 Correct 55 ms 9120 KB Output is correct
5 Correct 44 ms 9452 KB Output is correct
6 Correct 37 ms 9040 KB Output is correct
7 Correct 30 ms 7844 KB Output is correct
8 Correct 111 ms 35052 KB Output is correct
9 Correct 132 ms 35152 KB Output is correct
10 Correct 29 ms 7744 KB Output is correct
11 Correct 140 ms 44068 KB Output is correct
12 Correct 139 ms 44004 KB Output is correct
13 Correct 161 ms 43960 KB Output is correct
14 Correct 37 ms 7820 KB Output is correct
15 Correct 115 ms 35452 KB Output is correct
16 Correct 123 ms 35920 KB Output is correct
17 Correct 155 ms 36368 KB Output is correct
18 Correct 154 ms 36412 KB Output is correct
19 Correct 175 ms 40936 KB Output is correct
20 Correct 207 ms 40232 KB Output is correct
21 Correct 126 ms 35536 KB Output is correct
22 Correct 127 ms 35692 KB Output is correct
23 Correct 134 ms 35796 KB Output is correct
24 Correct 158 ms 35980 KB Output is correct
25 Correct 162 ms 37704 KB Output is correct
26 Correct 129 ms 35392 KB Output is correct
27 Correct 126 ms 35500 KB Output is correct
28 Correct 34 ms 7744 KB Output is correct
29 Correct 40 ms 8656 KB Output is correct
30 Correct 284 ms 8848 KB Output is correct
31 Correct 46 ms 8824 KB Output is correct
32 Correct 41 ms 9144 KB Output is correct
33 Correct 1173 ms 9052 KB Output is correct
34 Correct 31 ms 7744 KB Output is correct
35 Execution timed out 3556 ms 34824 KB Time limit exceeded
36 Halted 0 ms 0 KB -