oj.uz

Submission #401018

# Submission time Handle Problem Language Result Execution time Memory
401018 2021-05-09T07:34:25 Z errorgorn Inside information (BOI21_servers) C++17
5 / 100
 154 ms 34528 KB 
#include <bits/stdc++.h>
using namespace std;
 
#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){
	if (dsu.par(a)!=dsu.par(b)) return false;
	
	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;
		
		int b=mov(b,d[b]-d[g]-1);
		int a=mov(a,d[a]-d[g]-1);
		if (w[a]<w[b]) can=false;
		
		return can;
	}
}
 
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);
	
	//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<<in[x]<<" "; cout<<endl;
	//rep(x,1,n+1) cout<<out[x]<<" "; cout<<endl;
	
	for (auto &it:Q){
		if (it.c=='S'){
			dsu.unions(it.a,it.b);
		}
		else if (it.c=='Q'){
			if (reach(it.a,it.b)) cout<<"yes"<<endl;
			else cout<<"no"<<endl;
		}
		else{
			
		}
	}
}

Compilation message

servers.cpp: In function 'bool reach(int, int)':
servers.cpp:112:18: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |   int b=mov(b,d[b]-d[g]-1);
      |               ~~~^
servers.cpp:113:18: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |   int a=mov(a,d[a]-d[g]-1);
      |               ~~~^

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 14864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 14864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 14940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 14940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14864 KB Output is correct
2 Correct 154 ms 34528 KB Output is correct
3 Correct 146 ms 34500 KB Output is correct
4 Correct 143 ms 34436 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14864 KB Output is correct
2 Correct 154 ms 34528 KB Output is correct
3 Correct 146 ms 34500 KB Output is correct
4 Correct 143 ms 34436 KB Output is correct
5 Incorrect 37 ms 15664 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 14880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 14880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14904 KB Output is correct
2 Correct 148 ms 34516 KB Output is correct
3 Correct 147 ms 34524 KB Output is correct
4 Correct 140 ms 34500 KB Output is correct
5 Incorrect 41 ms 15792 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14904 KB Output is correct
2 Correct 148 ms 34516 KB Output is correct
3 Correct 147 ms 34524 KB Output is correct
4 Correct 140 ms 34500 KB Output is correct
5 Incorrect 41 ms 15792 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 14900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 14900 KB Output isn't correct
2 Halted 0 ms 0 KB -