oj.uz

답안 #574225

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
574225 2022-06-08T08:12:56 Z amunduzbaev Inside information (BOI21_servers) C++17
50 / 100
 405 ms 49204 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);
}

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());
	sort(qq[u].begin(), qq[u].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(face[pos[tot[j]]], 1);
			j++;
		}
		
		res[x] += tree.get(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 34 ms 12348 KB Output is correct
2 Correct 44 ms 13436 KB Output is correct
3 Correct 40 ms 13508 KB Output is correct
4 Correct 54 ms 13472 KB Output is correct
5 Correct 51 ms 13320 KB Output is correct
6 Correct 42 ms 13188 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 12348 KB Output is correct
2 Correct 44 ms 13436 KB Output is correct
3 Correct 40 ms 13508 KB Output is correct
4 Correct 54 ms 13472 KB Output is correct
5 Correct 51 ms 13320 KB Output is correct
6 Correct 42 ms 13188 KB Output is correct
7 Incorrect 35 ms 12888 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 12416 KB Output is correct
2 Correct 140 ms 41236 KB Output is correct
3 Correct 145 ms 41240 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 12416 KB Output is correct
2 Correct 140 ms 41236 KB Output is correct
3 Correct 145 ms 41240 KB Output is correct
4 Incorrect 39 ms 12872 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 12316 KB Output is correct
2 Correct 326 ms 48736 KB Output is correct
3 Correct 312 ms 48768 KB Output is correct
4 Correct 215 ms 49204 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 12316 KB Output is correct
2 Correct 326 ms 48736 KB Output is correct
3 Correct 312 ms 48768 KB Output is correct
4 Correct 215 ms 49204 KB Output is correct
5 Incorrect 33 ms 12864 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 12384 KB Output is correct
2 Correct 189 ms 40400 KB Output is correct
3 Correct 230 ms 40700 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 12384 KB Output is correct
2 Correct 189 ms 40400 KB Output is correct
3 Correct 230 ms 40700 KB Output is correct
4 Incorrect 34 ms 12840 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 12356 KB Output is correct
2 Correct 352 ms 48664 KB Output is correct
3 Correct 297 ms 48768 KB Output is correct
4 Correct 219 ms 49136 KB Output is correct
5 Correct 36 ms 12276 KB Output is correct
6 Correct 187 ms 40492 KB Output is correct
7 Correct 237 ms 40744 KB Output is correct
8 Correct 302 ms 40724 KB Output is correct
9 Correct 329 ms 41260 KB Output is correct
10 Correct 323 ms 45696 KB Output is correct
11 Correct 405 ms 44672 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 12356 KB Output is correct
2 Correct 352 ms 48664 KB Output is correct
3 Correct 297 ms 48768 KB Output is correct
4 Correct 219 ms 49136 KB Output is correct
5 Correct 36 ms 12276 KB Output is correct
6 Correct 187 ms 40492 KB Output is correct
7 Correct 237 ms 40744 KB Output is correct
8 Correct 302 ms 40724 KB Output is correct
9 Correct 329 ms 41260 KB Output is correct
10 Correct 323 ms 45696 KB Output is correct
11 Correct 405 ms 44672 KB Output is correct
12 Incorrect 31 ms 12868 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 12336 KB Output is correct
2 Correct 46 ms 13392 KB Output is correct
3 Correct 46 ms 13564 KB Output is correct
4 Correct 60 ms 13468 KB Output is correct
5 Correct 54 ms 13392 KB Output is correct
6 Correct 41 ms 13196 KB Output is correct
7 Correct 34 ms 12404 KB Output is correct
8 Correct 128 ms 41256 KB Output is correct
9 Correct 141 ms 41360 KB Output is correct
10 Correct 34 ms 12296 KB Output is correct
11 Correct 317 ms 48696 KB Output is correct
12 Correct 354 ms 48800 KB Output is correct
13 Correct 219 ms 49172 KB Output is correct
14 Correct 37 ms 12384 KB Output is correct
15 Correct 197 ms 40544 KB Output is correct
16 Correct 247 ms 40744 KB Output is correct
17 Correct 304 ms 40628 KB Output is correct
18 Correct 308 ms 41204 KB Output is correct
19 Correct 322 ms 45740 KB Output is correct
20 Correct 380 ms 44836 KB Output is correct
21 Correct 151 ms 41148 KB Output is correct
22 Correct 150 ms 40740 KB Output is correct
23 Correct 235 ms 40700 KB Output is correct
24 Correct 203 ms 40768 KB Output is correct
25 Correct 395 ms 45928 KB Output is correct
26 Correct 275 ms 40028 KB Output is correct
27 Correct 278 ms 40148 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 12336 KB Output is correct
2 Correct 46 ms 13392 KB Output is correct
3 Correct 46 ms 13564 KB Output is correct
4 Correct 60 ms 13468 KB Output is correct
5 Correct 54 ms 13392 KB Output is correct
6 Correct 41 ms 13196 KB Output is correct
7 Correct 34 ms 12404 KB Output is correct
8 Correct 128 ms 41256 KB Output is correct
9 Correct 141 ms 41360 KB Output is correct
10 Correct 34 ms 12296 KB Output is correct
11 Correct 317 ms 48696 KB Output is correct
12 Correct 354 ms 48800 KB Output is correct
13 Correct 219 ms 49172 KB Output is correct
14 Correct 37 ms 12384 KB Output is correct
15 Correct 197 ms 40544 KB Output is correct
16 Correct 247 ms 40744 KB Output is correct
17 Correct 304 ms 40628 KB Output is correct
18 Correct 308 ms 41204 KB Output is correct
19 Correct 322 ms 45740 KB Output is correct
20 Correct 380 ms 44836 KB Output is correct
21 Correct 151 ms 41148 KB Output is correct
22 Correct 150 ms 40740 KB Output is correct
23 Correct 235 ms 40700 KB Output is correct
24 Correct 203 ms 40768 KB Output is correct
25 Correct 395 ms 45928 KB Output is correct
26 Correct 275 ms 40028 KB Output is correct
27 Correct 278 ms 40148 KB Output is correct
28 Incorrect 34 ms 12888 KB Extra information in the output file
29 Halted 0 ms 0 KB -