oj.uz

답안 #574235

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
574235 2022-06-08T08:28:26 Z amunduzbaev Inside information (BOI21_servers) C++17
52.5 / 100
 432 ms 53432 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array

const int N = 3e5 + 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);
}

struct BIT{
	int tree[N];
	void add(int i, int v){
		for(;i<N;i+=(i&-i)) tree[i] += v;
	}
	
	int get(int i){
		int r = 0;
		for(;i>0;i-=(i&-i)) r += tree[i];
		return r;
	}
	
	int get(int l, int r){
		return get(r) - get(l - 1);
	}
}tree;

int res[N], used[N], sub[N];
int to[N], ver[N], pos[N];
vector<int> qq[N], tt, tot;
int face[N];

void dfs1(int u, int p = -1){
	sub[u] = 1;
	for(auto x : edges[u]){
		if(x[0] == p || used[x[0]]) continue;
		pos[x[1]] = x[0];
		to[x[0]] = x[1], dfs1(x[0], u);
		sub[u] += sub[x[0]];
	}
}

int cen(int u, int n, int p = -1){
	for(auto x : edges[u]){
		if(x[0] == p || used[x[0]]) continue;
		if(sub[x[0]] * 2 > n) return cen(x[0], n, u);
	} return u;
}

void dfs2(int u, int inc = 1, int dec = 1, int p = -1){
	if(dec){
		for(auto x : qq[u]){
			if(x < to[face[u]]) continue;
			tt.push_back(x);
			res[x]++;
		}
	}
	if(inc){
		tot.push_back(to[u]);
	}
	for(auto x : edges[u]){
		if(x[0] == p || used[x[0]]) continue;
		face[x[0]] = face[u];
		dfs2(x[0], inc & (to[u] < x[1]), dec & (to[u] > x[1]), u);
	}
}

void dec(int u){
	dfs1(u);
	u = cen(u, sub[u]);
	dfs1(u);
	
	tt.clear(), tot.clear();
	for(auto x : edges[u]){
		if(used[x[0]]) continue;
		face[x[0]] = x[0];
		dfs2(x[0], 1, 1, u);
	}
	
	sort(tt.begin(), tt.end());
	sort(tot.begin(), tot.end());
	
	for(auto x : qq[u]){
		int cc = upper_bound(tot.begin(), tot.end(), x) - tot.begin();
		res[x] += cc;
	}
	
	int j = 0;
	for(auto x : tt){ 
		while(j < (int)tot.size() && tot[j] < x){
			tree.add(to[face[pos[tot[j]]]], 1);
			j++;
		}
		
		res[x] += tree.get(to[face[ver[x]]] + 1, N - 1);
	}
	
	for(int l=0;l<j;l++) tree.add(face[pos[tot[l]]], -1);
	used[u] = 1;
	for(auto x : edges[u]){
		if(used[x[0]]) continue;
		dec(x[0]);
	}
}

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'){
			cin>>ver[i];
			qq[ver[i]].push_back(i);
			q.push_back({-1, ver[i], i});
		}
	}
	
	par[1][0] = 1;
	dfs(1);
	dec(1);
	
	for(auto [a, b, t] : q){
		if(~a){
			if(check(a, b, t)) cout<<"yes\n";
			else cout<<"no\n";
		} else { 
			cout<<++res[t]<<"\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

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 16560 KB Output is correct
2 Correct 49 ms 17612 KB Output is correct
3 Correct 41 ms 17760 KB Output is correct
4 Correct 56 ms 17700 KB Output is correct
5 Correct 51 ms 17592 KB Output is correct
6 Correct 45 ms 17388 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 16560 KB Output is correct
2 Correct 49 ms 17612 KB Output is correct
3 Correct 41 ms 17760 KB Output is correct
4 Correct 56 ms 17700 KB Output is correct
5 Correct 51 ms 17592 KB Output is correct
6 Correct 45 ms 17388 KB Output is correct
7 Incorrect 44 ms 17464 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 16580 KB Output is correct
2 Correct 157 ms 45456 KB Output is correct
3 Correct 153 ms 45420 KB Output is correct

Subtask #4
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 16580 KB Output is correct
2 Correct 157 ms 45456 KB Output is correct
3 Correct 153 ms 45420 KB Output is correct
4 Correct 36 ms 17436 KB Output is correct
5 Correct 158 ms 51212 KB Output is correct
6 Correct 150 ms 49784 KB Output is correct
7 Correct 139 ms 50852 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 16572 KB Output is correct
2 Correct 335 ms 52900 KB Output is correct
3 Correct 310 ms 52932 KB Output is correct
4 Correct 216 ms 53352 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 16572 KB Output is correct
2 Correct 335 ms 52900 KB Output is correct
3 Correct 310 ms 52932 KB Output is correct
4 Correct 216 ms 53352 KB Output is correct
5 Incorrect 35 ms 17560 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 16576 KB Output is correct
2 Correct 189 ms 44684 KB Output is correct
3 Correct 236 ms 44912 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 16576 KB Output is correct
2 Correct 189 ms 44684 KB Output is correct
3 Correct 236 ms 44912 KB Output is correct
4 Incorrect 38 ms 17476 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 16496 KB Output is correct
2 Correct 326 ms 52884 KB Output is correct
3 Correct 366 ms 52972 KB Output is correct
4 Correct 217 ms 53344 KB Output is correct
5 Correct 35 ms 16580 KB Output is correct
6 Correct 219 ms 44688 KB Output is correct
7 Correct 240 ms 44876 KB Output is correct
8 Correct 333 ms 44964 KB Output is correct
9 Correct 284 ms 45296 KB Output is correct
10 Correct 323 ms 49892 KB Output is correct
11 Correct 363 ms 48844 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 16496 KB Output is correct
2 Correct 326 ms 52884 KB Output is correct
3 Correct 366 ms 52972 KB Output is correct
4 Correct 217 ms 53344 KB Output is correct
5 Correct 35 ms 16580 KB Output is correct
6 Correct 219 ms 44688 KB Output is correct
7 Correct 240 ms 44876 KB Output is correct
8 Correct 333 ms 44964 KB Output is correct
9 Correct 284 ms 45296 KB Output is correct
10 Correct 323 ms 49892 KB Output is correct
11 Correct 363 ms 48844 KB Output is correct
12 Incorrect 37 ms 17352 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 16496 KB Output is correct
2 Correct 61 ms 17540 KB Output is correct
3 Correct 49 ms 17732 KB Output is correct
4 Correct 57 ms 17656 KB Output is correct
5 Correct 54 ms 17568 KB Output is correct
6 Correct 44 ms 17320 KB Output is correct
7 Correct 35 ms 16508 KB Output is correct
8 Correct 136 ms 45452 KB Output is correct
9 Correct 142 ms 45552 KB Output is correct
10 Correct 34 ms 16584 KB Output is correct
11 Correct 388 ms 52908 KB Output is correct
12 Correct 310 ms 52928 KB Output is correct
13 Correct 233 ms 53432 KB Output is correct
14 Correct 33 ms 16552 KB Output is correct
15 Correct 195 ms 44636 KB Output is correct
16 Correct 251 ms 44924 KB Output is correct
17 Correct 340 ms 44844 KB Output is correct
18 Correct 324 ms 45272 KB Output is correct
19 Correct 339 ms 49940 KB Output is correct
20 Correct 432 ms 48932 KB Output is correct
21 Correct 211 ms 45276 KB Output is correct
22 Correct 171 ms 45032 KB Output is correct
23 Correct 250 ms 44860 KB Output is correct
24 Correct 227 ms 44932 KB Output is correct
25 Correct 390 ms 50048 KB Output is correct
26 Correct 331 ms 44348 KB Output is correct
27 Correct 305 ms 44452 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 16496 KB Output is correct
2 Correct 61 ms 17540 KB Output is correct
3 Correct 49 ms 17732 KB Output is correct
4 Correct 57 ms 17656 KB Output is correct
5 Correct 54 ms 17568 KB Output is correct
6 Correct 44 ms 17320 KB Output is correct
7 Correct 35 ms 16508 KB Output is correct
8 Correct 136 ms 45452 KB Output is correct
9 Correct 142 ms 45552 KB Output is correct
10 Correct 34 ms 16584 KB Output is correct
11 Correct 388 ms 52908 KB Output is correct
12 Correct 310 ms 52928 KB Output is correct
13 Correct 233 ms 53432 KB Output is correct
14 Correct 33 ms 16552 KB Output is correct
15 Correct 195 ms 44636 KB Output is correct
16 Correct 251 ms 44924 KB Output is correct
17 Correct 340 ms 44844 KB Output is correct
18 Correct 324 ms 45272 KB Output is correct
19 Correct 339 ms 49940 KB Output is correct
20 Correct 432 ms 48932 KB Output is correct
21 Correct 211 ms 45276 KB Output is correct
22 Correct 171 ms 45032 KB Output is correct
23 Correct 250 ms 44860 KB Output is correct
24 Correct 227 ms 44932 KB Output is correct
25 Correct 390 ms 50048 KB Output is correct
26 Correct 331 ms 44348 KB Output is correct
27 Correct 305 ms 44452 KB Output is correct
28 Incorrect 54 ms 17376 KB Extra information in the output file
29 Halted 0 ms 0 KB -