oj.uz

Submission #401011

# Submission time Handle Problem Language Result Execution time Memory
401011 2021-05-09T06:50:23 Z errorgorn Inside information (BOI21_servers) C++17
50 / 100
 486 ms 52672 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 node{
	int s,e,m;
	int val=0;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int i,int j,int k){
		if (s==i && e==j) val+=k;
		else if (j<=m) l->update(i,j,k);
		else if (m<i) r->update(i,j,k);
		else l->update(i,m,k),r->update(m+1,j,k);
	}
	
	int query(int i){
		if (s==e) return val;
		if (i<=m) return val+l->query(i);
		else return val+r->query(i);
	}
} *root=new node(0,200005);

int n,k;
vector<ii> al[120005];
int in[120005];
int out[120005];

int d[120005];
int tkd[120005][20];

int asc[120005];
int dsc[120005];
int w[120005];

int TIME=1;

void dfs(int i,int p){
	in[i]=++TIME;
	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);
	}
	out[i]=TIME;
}

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;

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'){
			int temp;
			if (d[it.a]>d[it.b]) temp=it.a;
			else temp=it.b;
			
			root->update(in[temp],out[temp],1);
			
			//cout<<"upd: "<<temp<<endl;
			
			//rep(x,1,n+1) cout<<root->query(in[x])<<" "; cout<<endl;
		}
		else if (it.c=='Q'){
			//cout<<"query: "<<it.a<<" "<<it.b<<endl;
			
			int g=lca(it.a,it.b);
			
			int dist=d[it.a]+d[it.b]-2*d[g];
			int dist2=root->query(in[it.a])
						+root->query(in[it.b])
						-2*root->query(in[g]);
						
			//cout<<dist<<" "<<dist2<<endl;
			
			if (dist!=dist2){
				cout<<"no"<<endl;
				continue;
			}
			
			if (g==it.a){
				if (d[dsc[it.b]]<=d[g]) cout<<"yes"<<endl;
				else cout<<"no"<<endl;
			}
			else if (g==it.b){
				if (d[asc[it.a]]<=d[g]) cout<<"yes"<<endl;
				else cout<<"no"<<endl;
			}
			else{
				bool can=true;
				if (d[dsc[it.b]]>d[g]) can=false;
				if (d[asc[it.a]]>d[g]) can=false;
				
				int b=mov(it.b,d[it.b]-d[g]-1);
				int a=mov(it.a,d[it.a]-d[g]-1);
				if (w[a]<w[b]) can=false;
				
				if (can) cout<<"yes"<<endl;
				else cout<<"no"<<endl;
			}
		}
		else{
			
		}
	}
}

Compilation message

servers.cpp: In constructor 'node::node(int, int)':
servers.cpp:25:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 91 ms 33184 KB Output is correct
2 Correct 123 ms 34716 KB Output is correct
3 Correct 112 ms 34880 KB Output is correct
4 Correct 121 ms 34880 KB Output is correct
5 Correct 115 ms 35092 KB Output is correct
6 Correct 119 ms 34724 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 91 ms 33184 KB Output is correct
2 Correct 123 ms 34716 KB Output is correct
3 Correct 112 ms 34880 KB Output is correct
4 Correct 121 ms 34880 KB Output is correct
5 Correct 115 ms 35092 KB Output is correct
6 Correct 119 ms 34724 KB Output is correct
7 Incorrect 85 ms 34020 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 103 ms 33252 KB Output is correct
2 Correct 279 ms 44188 KB Output is correct
3 Correct 280 ms 43968 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 103 ms 33252 KB Output is correct
2 Correct 279 ms 44188 KB Output is correct
3 Correct 280 ms 43968 KB Output is correct
4 Incorrect 92 ms 34112 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 91 ms 33216 KB Output is correct
2 Correct 339 ms 52404 KB Output is correct
3 Correct 336 ms 52448 KB Output is correct
4 Correct 306 ms 52388 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 33216 KB Output is correct
2 Correct 339 ms 52404 KB Output is correct
3 Correct 336 ms 52448 KB Output is correct
4 Correct 306 ms 52388 KB Output is correct
5 Incorrect 94 ms 34056 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 86 ms 33136 KB Output is correct
2 Correct 298 ms 43920 KB Output is correct
3 Correct 309 ms 44444 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 33136 KB Output is correct
2 Correct 298 ms 43920 KB Output is correct
3 Correct 309 ms 44444 KB Output is correct
4 Incorrect 86 ms 34088 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 93 ms 33156 KB Output is correct
2 Correct 352 ms 52408 KB Output is correct
3 Correct 331 ms 52436 KB Output is correct
4 Correct 293 ms 52452 KB Output is correct
5 Correct 97 ms 34124 KB Output is correct
6 Correct 299 ms 43932 KB Output is correct
7 Correct 316 ms 44416 KB Output is correct
8 Correct 419 ms 44772 KB Output is correct
9 Correct 355 ms 45048 KB Output is correct
10 Correct 314 ms 49244 KB Output is correct
11 Correct 445 ms 48680 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 93 ms 33156 KB Output is correct
2 Correct 352 ms 52408 KB Output is correct
3 Correct 331 ms 52436 KB Output is correct
4 Correct 293 ms 52452 KB Output is correct
5 Correct 97 ms 34124 KB Output is correct
6 Correct 299 ms 43932 KB Output is correct
7 Correct 316 ms 44416 KB Output is correct
8 Correct 419 ms 44772 KB Output is correct
9 Correct 355 ms 45048 KB Output is correct
10 Correct 314 ms 49244 KB Output is correct
11 Correct 445 ms 48680 KB Output is correct
12 Incorrect 84 ms 34012 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 87 ms 33204 KB Output is correct
2 Correct 117 ms 34700 KB Output is correct
3 Correct 115 ms 34812 KB Output is correct
4 Correct 126 ms 34880 KB Output is correct
5 Correct 107 ms 35072 KB Output is correct
6 Correct 111 ms 34824 KB Output is correct
7 Correct 89 ms 34084 KB Output is correct
8 Correct 264 ms 44012 KB Output is correct
9 Correct 336 ms 44032 KB Output is correct
10 Correct 96 ms 34120 KB Output is correct
11 Correct 326 ms 52580 KB Output is correct
12 Correct 347 ms 52672 KB Output is correct
13 Correct 274 ms 52644 KB Output is correct
14 Correct 89 ms 34100 KB Output is correct
15 Correct 314 ms 44276 KB Output is correct
16 Correct 316 ms 44868 KB Output is correct
17 Correct 462 ms 45136 KB Output is correct
18 Correct 342 ms 45276 KB Output is correct
19 Correct 337 ms 49840 KB Output is correct
20 Correct 486 ms 49100 KB Output is correct
21 Correct 287 ms 44404 KB Output is correct
22 Correct 281 ms 44540 KB Output is correct
23 Correct 330 ms 44940 KB Output is correct
24 Correct 342 ms 44932 KB Output is correct
25 Correct 325 ms 46664 KB Output is correct
26 Correct 273 ms 44340 KB Output is correct
27 Correct 238 ms 44272 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 87 ms 33204 KB Output is correct
2 Correct 117 ms 34700 KB Output is correct
3 Correct 115 ms 34812 KB Output is correct
4 Correct 126 ms 34880 KB Output is correct
5 Correct 107 ms 35072 KB Output is correct
6 Correct 111 ms 34824 KB Output is correct
7 Correct 89 ms 34084 KB Output is correct
8 Correct 264 ms 44012 KB Output is correct
9 Correct 336 ms 44032 KB Output is correct
10 Correct 96 ms 34120 KB Output is correct
11 Correct 326 ms 52580 KB Output is correct
12 Correct 347 ms 52672 KB Output is correct
13 Correct 274 ms 52644 KB Output is correct
14 Correct 89 ms 34100 KB Output is correct
15 Correct 314 ms 44276 KB Output is correct
16 Correct 316 ms 44868 KB Output is correct
17 Correct 462 ms 45136 KB Output is correct
18 Correct 342 ms 45276 KB Output is correct
19 Correct 337 ms 49840 KB Output is correct
20 Correct 486 ms 49100 KB Output is correct
21 Correct 287 ms 44404 KB Output is correct
22 Correct 281 ms 44540 KB Output is correct
23 Correct 330 ms 44940 KB Output is correct
24 Correct 342 ms 44932 KB Output is correct
25 Correct 325 ms 46664 KB Output is correct
26 Correct 273 ms 44340 KB Output is correct
27 Correct 238 ms 44272 KB Output is correct
28 Incorrect 90 ms 33972 KB Extra information in the output file
29 Halted 0 ms 0 KB -