oj.uz

Submission #533109

# Submission time Handle Problem Language Result Execution time Memory
533109 2022-03-04T20:01:55 Z shayanebrahimi Inside information (BOI21_servers) C++11
5 / 100
 271 ms 38340 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];
	}
}
ll 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]=1e9;
	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 20036 KB Output is correct
2 Correct 39 ms 20504 KB Output is correct
3 Correct 37 ms 20620 KB Output is correct
4 Correct 42 ms 20476 KB Output is correct
5 Correct 40 ms 19968 KB Output is correct
6 Correct 39 ms 20608 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 20036 KB Output is correct
2 Correct 39 ms 20504 KB Output is correct
3 Correct 37 ms 20620 KB Output is correct
4 Correct 42 ms 20476 KB Output is correct
5 Correct 40 ms 19968 KB Output is correct
6 Correct 39 ms 20608 KB Output is correct
7 Correct 30 ms 19780 KB Output is correct
8 Correct 44 ms 20244 KB Output is correct
9 Correct 38 ms 19908 KB Output is correct
10 Correct 47 ms 20288 KB Output is correct
11 Correct 48 ms 19600 KB Output is correct
12 Correct 39 ms 19620 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 20164 KB Output is correct
2 Incorrect 137 ms 32848 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 20164 KB Output is correct
2 Incorrect 137 ms 32848 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 19976 KB Output is correct
2 Incorrect 194 ms 31912 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 19976 KB Output is correct
2 Incorrect 194 ms 31912 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 20172 KB Output is correct
2 Incorrect 271 ms 38240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 20172 KB Output is correct
2 Incorrect 271 ms 38240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 20036 KB Output is correct
2 Correct 41 ms 20476 KB Output is correct
3 Correct 39 ms 20692 KB Output is correct
4 Correct 41 ms 20532 KB Output is correct
5 Correct 40 ms 19956 KB Output is correct
6 Correct 39 ms 20560 KB Output is correct
7 Correct 42 ms 20148 KB Output is correct
8 Incorrect 142 ms 32848 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 20036 KB Output is correct
2 Correct 41 ms 20476 KB Output is correct
3 Correct 39 ms 20692 KB Output is correct
4 Correct 41 ms 20532 KB Output is correct
5 Correct 40 ms 19956 KB Output is correct
6 Correct 39 ms 20560 KB Output is correct
7 Correct 42 ms 20148 KB Output is correct
8 Incorrect 142 ms 32848 KB Output isn't correct
9 Halted 0 ms 0 KB -