oj.uz

Submission #533107

# Submission time Handle Problem Language Result Execution time Memory
533107 2022-03-04T19:50:29 Z shayanebrahimi Inside information (BOI21_servers) C++14
5 / 100
 303 ms 41668 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl                        '\n'
#define debug(e)                    cerr << #e << ": " <<  e << endl;
#define fast_io;                 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const ll MOD=1e9+7;//998244353//1e9+9//1111211111;
//ll tavmd(ll a,ll b){if(b==0){return 1;}if(b%2==0){ll x=tavmd(a,b/2);return(x*x)%MOD;}else{return(a%MOD*tavmd(a,b-1)%MOD)%MOD;}}
const ll MAXN=2e5+10;
const ll INF=8e18;
const ll LOG=30;
vector<pair<ll,ll>>adj[MAXN],Q[MAXN];
vector<ll>C[MAXN],updl;
ll qq[2*MAXN],sub[MAXN],bit[2*MAXN],tin[MAXN],ans[MAXN],n,k,cn,ccen,xy;
bool mark[MAXN];
void upd(ll k,ll v){
	while(k<2*MAXN){
		bit[k]+=v;
		k+=k&-k;
	}
}
ll sum(ll k){
	ll s=0;
	while(k>0){
		s+=bit[k];
		k-=k&-k;
	}
	return s;
}
void dfs0(ll u,ll p){
	sub[u]=1;
	for(auto e:adj[u]){
		if(e.first==p||mark[e.first])
                  continue;
		dfs0(e.first,u);
		sub[u]+=sub[e.first];
	}
}
int dfs1(ll u,ll p){
	for(auto e:adj[u]){
		if(e.first!=p&&!mark[e.first]&&sub[e.first]>cn/2){
			return dfs1(e.first,u);
		}
	}
	return u;
}
void inc(ll u,ll p,ll cw){
	tin[u]=cw;
	upd(cw+1,1);
	updl.push_back(cw);
	for(auto e:adj[u]){
		if(e.first!=p&&!mark[e.first]&&e.second>=cw){
			inc(e.first,u,e.second);
		}
	}
}
void dec(ll u,ll p,ll cw){
	for(auto q:Q[u]){
		if(q.first==ccen){
			if(xy<=q.second){
				ans[q.second]=1;
			}
			continue;
		}
		if(tin[q.first]<=q.second){
			ans[q.second]=1;
		}
	}
	for(auto c:C[u]){
		ans[c]+=sum(c+1);
		if(xy<=c)
                  ans[c]++;
	}
	for(auto e:adj[u]){
		if(e.first!=p&&!mark[e.first]&&e.second<=cw){
			dec(e.first,u,e.second);
		}
	}
}
void dfs4(ll u,ll p){
	tin[u]=INF;
	for(auto e:adj[u]){
		if(e.first==p||mark[e.first])
                  continue;
		dfs4(e.first,u);
	}
}
void decompose(ll u,ll p){
	dfs0(u,u);
	cn=sub[u];
	ll cen=dfs1(u, u);
	ccen=cen;
	sort(adj[cen].begin(),adj[cen].end(),[](const pair<ll,ll>&v1,const pair<ll,ll>&v2){
		return v1.second>v2.second;
	});
	for(auto e:adj[cen]){
		if(mark[e.first])
                  continue;
		xy=e.second;
		dec(e.first,cen,e.second);
		inc(e.first,cen,e.second);
	}
	for(auto q:Q[cen]){
		if(tin[q.first]<=q.second){
			ans[q.second]=1;
		}
	}
	for(auto c:C[cen]){
		ans[c]+=sum(c+1);
	}
	for(auto e:updl){
		upd(e+1,-1);
	}
	updl.clear();
	dfs4(cen,cen);
	mark[cen]=true;
	for(auto e:adj[cen]){
		if(mark[e.first])
                  continue;
		decompose(e.first,cen);
	}
}
int main(){
    fast_io;
	cin>>n>>k;
	for(int i=0;i<n+k-1;i++){
		char t;
		cin>>t;
		if(t=='S'){
			qq[i]=0;
			ll u,v;
			cin>>u>>v;
			u--;
			v--;
                  adj[u].push_back({v,i});
                  adj[v].push_back({u,i});
		}
		else if(t=='Q'){
			qq[i]=1;
			ll u,v;
			cin>>u>>v;
			u--;
			v--;
			if(u==v){
				ans[i]=1;
			}
			else
                        Q[v].push_back({u,i});
		}
		else{
			qq[i]=2;
			ll u;
			cin>>u;
			u--;
			C[u].push_back(i);
		}
	}
	dfs4(0,0);
	decompose(0,-1);
	for(int i=0;i<n+k-1;i++){
		if(qq[i]==0)
                  continue;
		if(qq[i]==1){
			if(ans[i]==1)
                        cout<<"yes"<<endl;
			else
                        cout<<"no"<<endl;
		}
		else{
			cout<<ans[i]+1<<endl;
		}
	}
    return 0;
}

Compilation message

servers.cpp:6:9: warning: ISO C++11 requires whitespace after the macro name
    6 | #define fast_io;                 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
      |         ^~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 20836 KB Output is correct
2 Correct 42 ms 21920 KB Output is correct
3 Correct 40 ms 22080 KB Output is correct
4 Correct 62 ms 21956 KB Output is correct
5 Correct 51 ms 21392 KB Output is correct
6 Correct 41 ms 21896 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 20836 KB Output is correct
2 Correct 42 ms 21920 KB Output is correct
3 Correct 40 ms 22080 KB Output is correct
4 Correct 62 ms 21956 KB Output is correct
5 Correct 51 ms 21392 KB Output is correct
6 Correct 41 ms 21896 KB Output is correct
7 Correct 32 ms 20692 KB Output is correct
8 Correct 46 ms 21424 KB Output is correct
9 Correct 47 ms 21060 KB Output is correct
10 Correct 50 ms 21504 KB Output is correct
11 Correct 43 ms 20764 KB Output is correct
12 Correct 39 ms 20720 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 21036 KB Output is correct
2 Incorrect 149 ms 35684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 21036 KB Output is correct
2 Incorrect 149 ms 35684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 20860 KB Output is correct
2 Incorrect 286 ms 41616 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 20860 KB Output is correct
2 Incorrect 286 ms 41616 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 20976 KB Output is correct
2 Incorrect 205 ms 35152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 20976 KB Output is correct
2 Incorrect 205 ms 35152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 20932 KB Output is correct
2 Incorrect 303 ms 41668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 20932 KB Output is correct
2 Incorrect 303 ms 41668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 20956 KB Output is correct
2 Correct 42 ms 21920 KB Output is correct
3 Correct 39 ms 22084 KB Output is correct
4 Correct 47 ms 21976 KB Output is correct
5 Correct 56 ms 21400 KB Output is correct
6 Correct 64 ms 21964 KB Output is correct
7 Correct 31 ms 21060 KB Output is correct
8 Incorrect 151 ms 35600 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 20956 KB Output is correct
2 Correct 42 ms 21920 KB Output is correct
3 Correct 39 ms 22084 KB Output is correct
4 Correct 47 ms 21976 KB Output is correct
5 Correct 56 ms 21400 KB Output is correct
6 Correct 64 ms 21964 KB Output is correct
7 Correct 31 ms 21060 KB Output is correct
8 Incorrect 151 ms 35600 KB Output isn't correct
9 Halted 0 ms 0 KB -