oj.uz

Submission #401407

# Submission time Handle Problem Language Result Execution time Memory
401407 2021-05-10T06:58:28 Z errorgorn Inside information (BOI21_servers) C++17
50 / 100
 1385 ms 102876 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;
	int curr=centp[i];
	
	while (curr!=-1){
		if (reach(curr,i)){
			res+=sz(s[curr])-s[curr].order_of_key(last(curr,i)+1)+1;
			//cout<<"que: "<<curr<<" "<<last(curr,i)<<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++;
			//cout<<endl;
		}
		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{
			cout<<que_c(it.a)<<endl;
		}
	}
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 26168 KB Output is correct
2 Correct 63 ms 26712 KB Output is correct
3 Correct 77 ms 26684 KB Output is correct
4 Correct 68 ms 26828 KB Output is correct
5 Correct 82 ms 27028 KB Output is correct
6 Correct 81 ms 26660 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 26168 KB Output is correct
2 Correct 63 ms 26712 KB Output is correct
3 Correct 77 ms 26684 KB Output is correct
4 Correct 68 ms 26828 KB Output is correct
5 Correct 82 ms 27028 KB Output is correct
6 Correct 81 ms 26660 KB Output is correct
7 Incorrect 52 ms 26136 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 53 ms 26164 KB Output is correct
2 Correct 364 ms 42608 KB Output is correct
3 Correct 319 ms 42608 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 26164 KB Output is correct
2 Correct 364 ms 42608 KB Output is correct
3 Correct 319 ms 42608 KB Output is correct
4 Incorrect 52 ms 26140 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 55 ms 26204 KB Output is correct
2 Correct 935 ms 53864 KB Output is correct
3 Correct 981 ms 53796 KB Output is correct
4 Correct 1078 ms 102696 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 26204 KB Output is correct
2 Correct 935 ms 53864 KB Output is correct
3 Correct 981 ms 53796 KB Output is correct
4 Correct 1078 ms 102696 KB Output is correct
5 Incorrect 50 ms 26164 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 50 ms 26104 KB Output is correct
2 Correct 889 ms 86488 KB Output is correct
3 Correct 594 ms 48468 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 26104 KB Output is correct
2 Correct 889 ms 86488 KB Output is correct
3 Correct 594 ms 48468 KB Output is correct
4 Incorrect 50 ms 26164 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 56 ms 26120 KB Output is correct
2 Correct 960 ms 53784 KB Output is correct
3 Correct 1010 ms 53944 KB Output is correct
4 Correct 1108 ms 102876 KB Output is correct
5 Correct 49 ms 26176 KB Output is correct
6 Correct 856 ms 86536 KB Output is correct
7 Correct 625 ms 48440 KB Output is correct
8 Correct 799 ms 47824 KB Output is correct
9 Correct 801 ms 47804 KB Output is correct
10 Correct 1137 ms 69872 KB Output is correct
11 Correct 1261 ms 69132 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 26120 KB Output is correct
2 Correct 960 ms 53784 KB Output is correct
3 Correct 1010 ms 53944 KB Output is correct
4 Correct 1108 ms 102876 KB Output is correct
5 Correct 49 ms 26176 KB Output is correct
6 Correct 856 ms 86536 KB Output is correct
7 Correct 625 ms 48440 KB Output is correct
8 Correct 799 ms 47824 KB Output is correct
9 Correct 801 ms 47804 KB Output is correct
10 Correct 1137 ms 69872 KB Output is correct
11 Correct 1261 ms 69132 KB Output is correct
12 Incorrect 50 ms 26168 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 49 ms 26148 KB Output is correct
2 Correct 65 ms 26700 KB Output is correct
3 Correct 76 ms 26728 KB Output is correct
4 Correct 67 ms 26756 KB Output is correct
5 Correct 74 ms 26868 KB Output is correct
6 Correct 75 ms 26588 KB Output is correct
7 Correct 60 ms 26152 KB Output is correct
8 Correct 326 ms 42624 KB Output is correct
9 Correct 355 ms 42536 KB Output is correct
10 Correct 48 ms 26124 KB Output is correct
11 Correct 1000 ms 53760 KB Output is correct
12 Correct 960 ms 53732 KB Output is correct
13 Correct 1096 ms 102600 KB Output is correct
14 Correct 50 ms 26180 KB Output is correct
15 Correct 879 ms 86512 KB Output is correct
16 Correct 622 ms 48496 KB Output is correct
17 Correct 910 ms 47864 KB Output is correct
18 Correct 850 ms 48012 KB Output is correct
19 Correct 1332 ms 69832 KB Output is correct
20 Correct 1385 ms 69120 KB Output is correct
21 Correct 360 ms 45164 KB Output is correct
22 Correct 365 ms 44124 KB Output is correct
23 Correct 600 ms 47624 KB Output is correct
24 Correct 626 ms 47856 KB Output is correct
25 Correct 1098 ms 48828 KB Output is correct
26 Correct 575 ms 43444 KB Output is correct
27 Correct 481 ms 42960 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 26148 KB Output is correct
2 Correct 65 ms 26700 KB Output is correct
3 Correct 76 ms 26728 KB Output is correct
4 Correct 67 ms 26756 KB Output is correct
5 Correct 74 ms 26868 KB Output is correct
6 Correct 75 ms 26588 KB Output is correct
7 Correct 60 ms 26152 KB Output is correct
8 Correct 326 ms 42624 KB Output is correct
9 Correct 355 ms 42536 KB Output is correct
10 Correct 48 ms 26124 KB Output is correct
11 Correct 1000 ms 53760 KB Output is correct
12 Correct 960 ms 53732 KB Output is correct
13 Correct 1096 ms 102600 KB Output is correct
14 Correct 50 ms 26180 KB Output is correct
15 Correct 879 ms 86512 KB Output is correct
16 Correct 622 ms 48496 KB Output is correct
17 Correct 910 ms 47864 KB Output is correct
18 Correct 850 ms 48012 KB Output is correct
19 Correct 1332 ms 69832 KB Output is correct
20 Correct 1385 ms 69120 KB Output is correct
21 Correct 360 ms 45164 KB Output is correct
22 Correct 365 ms 44124 KB Output is correct
23 Correct 600 ms 47624 KB Output is correct
24 Correct 626 ms 47856 KB Output is correct
25 Correct 1098 ms 48828 KB Output is correct
26 Correct 575 ms 43444 KB Output is correct
27 Correct 481 ms 42960 KB Output is correct
28 Incorrect 52 ms 26200 KB Extra information in the output file
29 Halted 0 ms 0 KB -