oj.uz

Submission #401405

# Submission time Handle Problem Language Result Execution time Memory
401405 2021-05-10T06:47:55 Z errorgorn Inside information (BOI21_servers) C++17
50 / 100
 1243 ms 102940 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'
 
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
 
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e)?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
 
struct DSU{
	int p[120005];
	
	DSU(){
		rep(x,0,120005) p[x]=x;
	}
	
	int par(int i){
		if (p[i]==i) return i;
		else return p[i]=par(p[i]);
	}
	
	void unions(int i,int j){
		i=par(i),j=par(j);
		p[i]=j;
	}
} dsu=DSU();
 
int n,k;
vector<ii> al[120005];
 
int d[120005];
int tkd[120005][20];
 
int asc[120005];
int dsc[120005];
int w[120005];
 
void dfs(int i,int p){
	for (auto &it:al[i]){
		if (it.fi==p) continue;
		w[it.fi]=it.se;
		
		asc[it.fi]=dsc[it.fi]=i;
		if (w[it.fi]>w[i]) asc[it.fi]=asc[i];
		else dsc[it.fi]=dsc[i];
		
		d[it.fi]=d[i]+1;
		
		int curr=tkd[it.fi][0]=i;
		rep(x,0,20){
			if (curr==-1) break;
			curr=tkd[it.fi][x+1]=tkd[curr][x];
		}
		
		dfs(it.fi,i);
	}
}
 
int mov(int i,int j){
	rep(bit,0,20) if (j&(1<<bit)){
		i=tkd[i][bit];
	}
	return i;
}
 
int lca(int i,int j){
	if (d[i]<d[j]) swap(i,j);
	i=mov(i,d[i]-d[j]);
	if (i==j) return i;
	
	rep(x,20,0){
		if (tkd[i][x]!=tkd[j][x]) i=tkd[i][x],j=tkd[j][x];
	}
	
	return tkd[i][0];
}
 
struct dat{
	char c;
	int a,b;
};
 
vector<dat> Q;
 
bool reach(int a,int b){ //is a->b decreasing
	int g=lca(a,b);
			
	if (g==a){
		if (d[dsc[b]]<=d[g]) return true;
		else return false;
	}
	else if (g==b){
		if (d[asc[a]]<=d[g]) return true;
		else return false;
	}
	else{
		bool can=true;
		if (d[dsc[b]]>d[g]) can=false;
		if (d[asc[a]]>d[g]) can=false;
		
		b=mov(b,d[b]-d[g]-1);
		a=mov(a,d[a]-d[g]-1);
		if (w[a]<w[b]) can=false;
		
		return can;
	}
}

int last(int a,int b){ 
	int g=lca(a,b);
	
	if (g==a) return w[mov(b,d[b]-d[a]-1)];
	else return w[a];
}

bool used[120005];
int ss[120005];
int centp[120005];

void dfs_sz(int i,int p){
	ss[i]=1;
	for (auto &it:al[i]){
		if (used[it.fi] || it.fi==p) continue;
		dfs_sz(it.fi,i);
		ss[i]+=ss[it.fi];
	}
}

void dfs_c(int i,int p){
	dfs_sz(i,-1);
	
	int currp=i;
	int curr=i;
	int sz=ss[i];
	while (true){
		for (auto &it:al[curr]){
			if (used[it.fi] || it.fi==currp) continue;
			
			if (ss[it.fi]>sz/2){
				currp=curr;
				curr=it.fi;
				goto reloop;
			}
		}
		break;
		reloop:;
	}
	
	centp[curr]=p;
	used[curr]=true;
	
	for (auto &it:al[curr]) if (!used[it.fi]) dfs_c(it.fi,curr);
}

#define indexed_set tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

indexed_set s[120005];

void upd_c(int i,int j){
	int curr=centp[i];
	
	while (curr!=-1){
		if (reach(i,curr) && last(i,curr)==j){
			s[curr].insert(last(curr,i));
			//cout<<"add: "<<curr<<" "<<last(curr,i)<<endl;
		}
		
		curr=centp[curr];
	}
}

int que_c(int i){
	int res=0;
	res+=sz(s[i])+1;
	//cout<<"que: "<<i<<" "<<0<<endl;
	int curr=centp[i];
	
	while (curr!=-1){
		if (reach(curr,i)){
			res+=sz(s[curr])-s[curr].order_of_key(last(i,curr)+1)+1;
			//cout<<"que: "<<curr<<" "<<last(i,curr)+1<<endl;
		}
		
		curr=centp[curr];
	}
	
	return res;
}
 
int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k;
	
	char c;
	int a,b;
	
	int IDX=0;
	rep(x,0,n+k-1){
		cin>>c;
		
		if (c=='S'){
			cin>>a>>b;
			Q.pub({c,a,b});
			al[a].pub(ii(b,IDX));
			al[b].pub(ii(a,IDX));
			IDX++;
		}
		else if (c=='Q'){
			cin>>a>>b;
			Q.pub({c,a,b});
		}
		else{
			cin>>a;
			Q.pub({c,a,0});
		}
	}
	
	memset(tkd,-1,sizeof(tkd));
	asc[1]=dsc[1]=1;
	dfs(1,-1);
	dfs_c(1,-1);
	
	
	//rep(x,1,n+1) cout<<w[x]<<" "; cout<<endl;
	//rep(x,1,n+1) cout<<asc[x]<<" "; cout<<endl;
	//rep(x,1,n+1) cout<<dsc[x]<<" "; cout<<endl;
	//rep(x,1,n+1) cout<<d[x]<<" "; cout<<endl;
	//rep(x,1,n+1) cout<<centp[x]<<" "; cout<<endl;
	
	IDX=0;
	for (auto &it:Q){
		if (it.c=='S'){
			dsu.unions(it.a,it.b);
			
			upd_c(it.a,IDX);
			upd_c(it.b,IDX);
			IDX++;
		}
		else if (it.c=='Q'){
			if (dsu.par(it.a)==dsu.par(it.b) && 
				reach(it.a,it.b)) cout<<"yes"<<endl;
			else cout<<"no"<<endl;
		}
		else if (it.c=='C'){
			cout<<que_c(it.a)<<endl;
		}
	}
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 26172 KB Output is correct
2 Correct 72 ms 27048 KB Output is correct
3 Correct 77 ms 26984 KB Output is correct
4 Correct 66 ms 27072 KB Output is correct
5 Correct 74 ms 27268 KB Output is correct
6 Correct 75 ms 26952 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 26172 KB Output is correct
2 Correct 72 ms 27048 KB Output is correct
3 Correct 77 ms 26984 KB Output is correct
4 Correct 66 ms 27072 KB Output is correct
5 Correct 74 ms 27268 KB Output is correct
6 Correct 75 ms 26952 KB Output is correct
7 Incorrect 51 ms 26144 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 61 ms 26192 KB Output is correct
2 Correct 331 ms 42956 KB Output is correct
3 Correct 349 ms 42980 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 26192 KB Output is correct
2 Correct 331 ms 42956 KB Output is correct
3 Correct 349 ms 42980 KB Output is correct
4 Incorrect 52 ms 26172 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 49 ms 26152 KB Output is correct
2 Correct 944 ms 54140 KB Output is correct
3 Correct 952 ms 54188 KB Output is correct
4 Correct 1079 ms 102644 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 26152 KB Output is correct
2 Correct 944 ms 54140 KB Output is correct
3 Correct 952 ms 54188 KB Output is correct
4 Correct 1079 ms 102644 KB Output is correct
5 Incorrect 49 ms 26112 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 26120 KB Output is correct
2 Correct 870 ms 86560 KB Output is correct
3 Correct 607 ms 48392 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 26120 KB Output is correct
2 Correct 870 ms 86560 KB Output is correct
3 Correct 607 ms 48392 KB Output is correct
4 Incorrect 61 ms 26132 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 59 ms 26116 KB Output is correct
2 Correct 962 ms 53808 KB Output is correct
3 Correct 927 ms 53864 KB Output is correct
4 Correct 1067 ms 102632 KB Output is correct
5 Correct 49 ms 26192 KB Output is correct
6 Correct 867 ms 86552 KB Output is correct
7 Correct 602 ms 48468 KB Output is correct
8 Correct 820 ms 47724 KB Output is correct
9 Correct 794 ms 47756 KB Output is correct
10 Correct 1210 ms 70116 KB Output is correct
11 Correct 1230 ms 69148 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 26116 KB Output is correct
2 Correct 962 ms 53808 KB Output is correct
3 Correct 927 ms 53864 KB Output is correct
4 Correct 1067 ms 102632 KB Output is correct
5 Correct 49 ms 26192 KB Output is correct
6 Correct 867 ms 86552 KB Output is correct
7 Correct 602 ms 48468 KB Output is correct
8 Correct 820 ms 47724 KB Output is correct
9 Correct 794 ms 47756 KB Output is correct
10 Correct 1210 ms 70116 KB Output is correct
11 Correct 1230 ms 69148 KB Output is correct
12 Incorrect 50 ms 26088 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 26164 KB Output is correct
2 Correct 71 ms 26712 KB Output is correct
3 Correct 78 ms 26732 KB Output is correct
4 Correct 66 ms 26744 KB Output is correct
5 Correct 75 ms 26940 KB Output is correct
6 Correct 74 ms 26584 KB Output is correct
7 Correct 51 ms 26196 KB Output is correct
8 Correct 317 ms 42572 KB Output is correct
9 Correct 317 ms 42584 KB Output is correct
10 Correct 48 ms 26140 KB Output is correct
11 Correct 932 ms 53720 KB Output is correct
12 Correct 974 ms 54096 KB Output is correct
13 Correct 1084 ms 102940 KB Output is correct
14 Correct 49 ms 26172 KB Output is correct
15 Correct 860 ms 86408 KB Output is correct
16 Correct 643 ms 48452 KB Output is correct
17 Correct 798 ms 47852 KB Output is correct
18 Correct 792 ms 47852 KB Output is correct
19 Correct 1214 ms 69924 KB Output is correct
20 Correct 1243 ms 69268 KB Output is correct
21 Correct 324 ms 45148 KB Output is correct
22 Correct 324 ms 44188 KB Output is correct
23 Correct 580 ms 47652 KB Output is correct
24 Correct 571 ms 48024 KB Output is correct
25 Correct 883 ms 48748 KB Output is correct
26 Correct 520 ms 43376 KB Output is correct
27 Correct 473 ms 42860 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 26164 KB Output is correct
2 Correct 71 ms 26712 KB Output is correct
3 Correct 78 ms 26732 KB Output is correct
4 Correct 66 ms 26744 KB Output is correct
5 Correct 75 ms 26940 KB Output is correct
6 Correct 74 ms 26584 KB Output is correct
7 Correct 51 ms 26196 KB Output is correct
8 Correct 317 ms 42572 KB Output is correct
9 Correct 317 ms 42584 KB Output is correct
10 Correct 48 ms 26140 KB Output is correct
11 Correct 932 ms 53720 KB Output is correct
12 Correct 974 ms 54096 KB Output is correct
13 Correct 1084 ms 102940 KB Output is correct
14 Correct 49 ms 26172 KB Output is correct
15 Correct 860 ms 86408 KB Output is correct
16 Correct 643 ms 48452 KB Output is correct
17 Correct 798 ms 47852 KB Output is correct
18 Correct 792 ms 47852 KB Output is correct
19 Correct 1214 ms 69924 KB Output is correct
20 Correct 1243 ms 69268 KB Output is correct
21 Correct 324 ms 45148 KB Output is correct
22 Correct 324 ms 44188 KB Output is correct
23 Correct 580 ms 47652 KB Output is correct
24 Correct 571 ms 48024 KB Output is correct
25 Correct 883 ms 48748 KB Output is correct
26 Correct 520 ms 43376 KB Output is correct
27 Correct 473 ms 42860 KB Output is correct
28 Incorrect 52 ms 26196 KB Extra information in the output file
29 Halted 0 ms 0 KB -