oj.uz

Submission #533108

# Submission time Handle Problem Language Result Execution time Memory
533108 2022-03-04T19:52:52 Z shayanebrahimi Inside information (BOI21_servers) C++14
5 / 100
 337 ms 38476 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]=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 32 ms 20164 KB Output is correct
2 Correct 54 ms 20588 KB Output is correct
3 Correct 43 ms 20744 KB Output is correct
4 Correct 57 ms 20680 KB Output is correct
5 Correct 44 ms 20092 KB Output is correct
6 Correct 41 ms 20740 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 20164 KB Output is correct
2 Correct 54 ms 20588 KB Output is correct
3 Correct 43 ms 20744 KB Output is correct
4 Correct 57 ms 20680 KB Output is correct
5 Correct 44 ms 20092 KB Output is correct
6 Correct 41 ms 20740 KB Output is correct
7 Correct 32 ms 19908 KB Output is correct
8 Correct 46 ms 20640 KB Output is correct
9 Correct 44 ms 20496 KB Output is correct
10 Correct 45 ms 20676 KB Output is correct
11 Correct 44 ms 19948 KB Output is correct
12 Correct 40 ms 20036 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 20280 KB Output is correct
2 Incorrect 159 ms 32916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 20280 KB Output is correct
2 Incorrect 159 ms 32916 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 20164 KB Output is correct
2 Incorrect 297 ms 38404 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 20164 KB Output is correct
2 Incorrect 297 ms 38404 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 20088 KB Output is correct
2 Incorrect 337 ms 38476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 20088 KB Output is correct
2 Incorrect 337 ms 38476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 20132 KB Output is correct
2 Correct 41 ms 20664 KB Output is correct
3 Correct 40 ms 20800 KB Output is correct
4 Correct 60 ms 20616 KB Output is correct
5 Correct 51 ms 20164 KB Output is correct
6 Correct 51 ms 20732 KB Output is correct
7 Correct 31 ms 20268 KB Output is correct
8 Incorrect 189 ms 32936 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 20132 KB Output is correct
2 Correct 41 ms 20664 KB Output is correct
3 Correct 40 ms 20800 KB Output is correct
4 Correct 60 ms 20616 KB Output is correct
5 Correct 51 ms 20164 KB Output is correct
6 Correct 51 ms 20732 KB Output is correct
7 Correct 31 ms 20268 KB Output is correct
8 Incorrect 189 ms 32936 KB Output isn't correct
9 Halted 0 ms 0 KB -