oj.uz

Submission #401403

# Submission time Handle Problem Language Result Execution time Memory
401403 2021-05-10T06:45:17 Z errorgorn Inside information (BOI21_servers) C++17
50 / 100
 1439 ms 106048 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{
			cout<<que_c(it.a)<<endl;
		}
	}
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 26088 KB Output is correct
2 Correct 65 ms 28092 KB Output is correct
3 Correct 77 ms 28024 KB Output is correct
4 Correct 65 ms 28220 KB Output is correct
5 Correct 77 ms 28320 KB Output is correct
6 Correct 77 ms 27992 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 26088 KB Output is correct
2 Correct 65 ms 28092 KB Output is correct
3 Correct 77 ms 28024 KB Output is correct
4 Correct 65 ms 28220 KB Output is correct
5 Correct 77 ms 28320 KB Output is correct
6 Correct 77 ms 27992 KB Output is correct
7 Incorrect 51 ms 26980 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 52 ms 26168 KB Output is correct
2 Correct 336 ms 45424 KB Output is correct
3 Correct 320 ms 45496 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 26168 KB Output is correct
2 Correct 336 ms 45424 KB Output is correct
3 Correct 320 ms 45496 KB Output is correct
4 Incorrect 55 ms 26988 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 48 ms 26144 KB Output is correct
2 Correct 1008 ms 57076 KB Output is correct
3 Correct 1032 ms 57200 KB Output is correct
4 Correct 1133 ms 105876 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 26144 KB Output is correct
2 Correct 1008 ms 57076 KB Output is correct
3 Correct 1032 ms 57200 KB Output is correct
4 Correct 1133 ms 105876 KB Output is correct
5 Incorrect 52 ms 26996 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 65 ms 26108 KB Output is correct
2 Correct 913 ms 89720 KB Output is correct
3 Correct 735 ms 51760 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 26108 KB Output is correct
2 Correct 913 ms 89720 KB Output is correct
3 Correct 735 ms 51760 KB Output is correct
4 Incorrect 58 ms 27052 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 54 ms 26132 KB Output is correct
2 Correct 1140 ms 57160 KB Output is correct
3 Correct 1072 ms 57160 KB Output is correct
4 Correct 1095 ms 106048 KB Output is correct
5 Correct 52 ms 27044 KB Output is correct
6 Correct 922 ms 89768 KB Output is correct
7 Correct 682 ms 51776 KB Output is correct
8 Correct 857 ms 51072 KB Output is correct
9 Correct 847 ms 51280 KB Output is correct
10 Correct 1317 ms 73260 KB Output is correct
11 Correct 1439 ms 72584 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 26132 KB Output is correct
2 Correct 1140 ms 57160 KB Output is correct
3 Correct 1072 ms 57160 KB Output is correct
4 Correct 1095 ms 106048 KB Output is correct
5 Correct 52 ms 27044 KB Output is correct
6 Correct 922 ms 89768 KB Output is correct
7 Correct 682 ms 51776 KB Output is correct
8 Correct 857 ms 51072 KB Output is correct
9 Correct 847 ms 51280 KB Output is correct
10 Correct 1317 ms 73260 KB Output is correct
11 Correct 1439 ms 72584 KB Output is correct
12 Incorrect 51 ms 27048 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 51 ms 26156 KB Output is correct
2 Correct 68 ms 28072 KB Output is correct
3 Correct 80 ms 28092 KB Output is correct
4 Correct 70 ms 28236 KB Output is correct
5 Correct 78 ms 28356 KB Output is correct
6 Correct 78 ms 27976 KB Output is correct
7 Correct 53 ms 27016 KB Output is correct
8 Correct 329 ms 45408 KB Output is correct
9 Correct 338 ms 45580 KB Output is correct
10 Correct 50 ms 27052 KB Output is correct
11 Correct 982 ms 57124 KB Output is correct
12 Correct 980 ms 57128 KB Output is correct
13 Correct 1097 ms 106020 KB Output is correct
14 Correct 53 ms 27056 KB Output is correct
15 Correct 870 ms 89860 KB Output is correct
16 Correct 618 ms 51748 KB Output is correct
17 Correct 828 ms 51028 KB Output is correct
18 Correct 824 ms 51028 KB Output is correct
19 Correct 1270 ms 73244 KB Output is correct
20 Correct 1285 ms 72432 KB Output is correct
21 Correct 332 ms 48492 KB Output is correct
22 Correct 322 ms 47464 KB Output is correct
23 Correct 576 ms 50912 KB Output is correct
24 Correct 567 ms 51184 KB Output is correct
25 Correct 879 ms 52072 KB Output is correct
26 Correct 512 ms 46836 KB Output is correct
27 Correct 474 ms 46296 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 26156 KB Output is correct
2 Correct 68 ms 28072 KB Output is correct
3 Correct 80 ms 28092 KB Output is correct
4 Correct 70 ms 28236 KB Output is correct
5 Correct 78 ms 28356 KB Output is correct
6 Correct 78 ms 27976 KB Output is correct
7 Correct 53 ms 27016 KB Output is correct
8 Correct 329 ms 45408 KB Output is correct
9 Correct 338 ms 45580 KB Output is correct
10 Correct 50 ms 27052 KB Output is correct
11 Correct 982 ms 57124 KB Output is correct
12 Correct 980 ms 57128 KB Output is correct
13 Correct 1097 ms 106020 KB Output is correct
14 Correct 53 ms 27056 KB Output is correct
15 Correct 870 ms 89860 KB Output is correct
16 Correct 618 ms 51748 KB Output is correct
17 Correct 828 ms 51028 KB Output is correct
18 Correct 824 ms 51028 KB Output is correct
19 Correct 1270 ms 73244 KB Output is correct
20 Correct 1285 ms 72432 KB Output is correct
21 Correct 332 ms 48492 KB Output is correct
22 Correct 322 ms 47464 KB Output is correct
23 Correct 576 ms 50912 KB Output is correct
24 Correct 567 ms 51184 KB Output is correct
25 Correct 879 ms 52072 KB Output is correct
26 Correct 512 ms 46836 KB Output is correct
27 Correct 474 ms 46296 KB Output is correct
28 Incorrect 53 ms 27036 KB Extra information in the output file
29 Halted 0 ms 0 KB -