oj.uz

Submission #533206

# Submission time Handle Problem Language Result Execution time Memory
533206 2022-03-05T06:31:12 Z shayanebrahimi Inside information (BOI21_servers) C++14
100 / 100
 476 ms 42560 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[2*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 33 ms 20936 KB Output is correct
2 Correct 44 ms 21900 KB Output is correct
3 Correct 45 ms 22028 KB Output is correct
4 Correct 48 ms 21944 KB Output is correct
5 Correct 50 ms 21324 KB Output is correct
6 Correct 56 ms 21952 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 20936 KB Output is correct
2 Correct 44 ms 21900 KB Output is correct
3 Correct 45 ms 22028 KB Output is correct
4 Correct 48 ms 21944 KB Output is correct
5 Correct 50 ms 21324 KB Output is correct
6 Correct 56 ms 21952 KB Output is correct
7 Correct 34 ms 20720 KB Output is correct
8 Correct 46 ms 21440 KB Output is correct
9 Correct 41 ms 21100 KB Output is correct
10 Correct 55 ms 21512 KB Output is correct
11 Correct 48 ms 20728 KB Output is correct
12 Correct 40 ms 20676 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 21136 KB Output is correct
2 Correct 146 ms 35936 KB Output is correct
3 Correct 175 ms 36084 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 21136 KB Output is correct
2 Correct 146 ms 35936 KB Output is correct
3 Correct 175 ms 36084 KB Output is correct
4 Correct 36 ms 20708 KB Output is correct
5 Correct 139 ms 35504 KB Output is correct
6 Correct 98 ms 32944 KB Output is correct
7 Correct 105 ms 33232 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 20964 KB Output is correct
2 Correct 271 ms 41964 KB Output is correct
3 Correct 304 ms 41916 KB Output is correct
4 Correct 223 ms 42556 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 20964 KB Output is correct
2 Correct 271 ms 41964 KB Output is correct
3 Correct 304 ms 41916 KB Output is correct
4 Correct 223 ms 42556 KB Output is correct
5 Correct 33 ms 20720 KB Output is correct
6 Correct 323 ms 41916 KB Output is correct
7 Correct 253 ms 42204 KB Output is correct
8 Correct 313 ms 41500 KB Output is correct
9 Correct 300 ms 41596 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 20928 KB Output is correct
2 Correct 211 ms 35392 KB Output is correct
3 Correct 264 ms 34484 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 20928 KB Output is correct
2 Correct 211 ms 35392 KB Output is correct
3 Correct 264 ms 34484 KB Output is correct
4 Correct 33 ms 20804 KB Output is correct
5 Correct 237 ms 35308 KB Output is correct
6 Correct 244 ms 34472 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 20940 KB Output is correct
2 Correct 292 ms 42020 KB Output is correct
3 Correct 321 ms 41924 KB Output is correct
4 Correct 219 ms 42560 KB Output is correct
5 Correct 34 ms 20940 KB Output is correct
6 Correct 208 ms 35416 KB Output is correct
7 Correct 244 ms 34376 KB Output is correct
8 Correct 246 ms 34564 KB Output is correct
9 Correct 262 ms 35792 KB Output is correct
10 Correct 290 ms 38688 KB Output is correct
11 Correct 287 ms 37720 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 20940 KB Output is correct
2 Correct 292 ms 42020 KB Output is correct
3 Correct 321 ms 41924 KB Output is correct
4 Correct 219 ms 42560 KB Output is correct
5 Correct 34 ms 20940 KB Output is correct
6 Correct 208 ms 35416 KB Output is correct
7 Correct 244 ms 34376 KB Output is correct
8 Correct 246 ms 34564 KB Output is correct
9 Correct 262 ms 35792 KB Output is correct
10 Correct 290 ms 38688 KB Output is correct
11 Correct 287 ms 37720 KB Output is correct
12 Correct 33 ms 20676 KB Output is correct
13 Correct 300 ms 41892 KB Output is correct
14 Correct 247 ms 42248 KB Output is correct
15 Correct 325 ms 41484 KB Output is correct
16 Correct 286 ms 41376 KB Output is correct
17 Correct 34 ms 20840 KB Output is correct
18 Correct 291 ms 35308 KB Output is correct
19 Correct 229 ms 34424 KB Output is correct
20 Correct 264 ms 35140 KB Output is correct
21 Correct 258 ms 35776 KB Output is correct
22 Correct 380 ms 37560 KB Output is correct
23 Correct 476 ms 38008 KB Output is correct
24 Correct 423 ms 37024 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 20944 KB Output is correct
2 Correct 42 ms 21864 KB Output is correct
3 Correct 40 ms 22036 KB Output is correct
4 Correct 50 ms 21872 KB Output is correct
5 Correct 44 ms 21400 KB Output is correct
6 Correct 41 ms 21920 KB Output is correct
7 Correct 31 ms 21032 KB Output is correct
8 Correct 158 ms 36016 KB Output is correct
9 Correct 165 ms 36064 KB Output is correct
10 Correct 33 ms 20988 KB Output is correct
11 Correct 304 ms 41964 KB Output is correct
12 Correct 295 ms 41916 KB Output is correct
13 Correct 215 ms 42556 KB Output is correct
14 Correct 35 ms 21064 KB Output is correct
15 Correct 191 ms 35396 KB Output is correct
16 Correct 252 ms 34368 KB Output is correct
17 Correct 235 ms 34644 KB Output is correct
18 Correct 238 ms 35804 KB Output is correct
19 Correct 281 ms 38544 KB Output is correct
20 Correct 266 ms 37700 KB Output is correct
21 Correct 177 ms 35524 KB Output is correct
22 Correct 165 ms 35604 KB Output is correct
23 Correct 205 ms 35280 KB Output is correct
24 Correct 197 ms 35424 KB Output is correct
25 Correct 330 ms 38828 KB Output is correct
26 Correct 291 ms 33076 KB Output is correct
27 Correct 256 ms 32940 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 20944 KB Output is correct
2 Correct 42 ms 21864 KB Output is correct
3 Correct 40 ms 22036 KB Output is correct
4 Correct 50 ms 21872 KB Output is correct
5 Correct 44 ms 21400 KB Output is correct
6 Correct 41 ms 21920 KB Output is correct
7 Correct 31 ms 21032 KB Output is correct
8 Correct 158 ms 36016 KB Output is correct
9 Correct 165 ms 36064 KB Output is correct
10 Correct 33 ms 20988 KB Output is correct
11 Correct 304 ms 41964 KB Output is correct
12 Correct 295 ms 41916 KB Output is correct
13 Correct 215 ms 42556 KB Output is correct
14 Correct 35 ms 21064 KB Output is correct
15 Correct 191 ms 35396 KB Output is correct
16 Correct 252 ms 34368 KB Output is correct
17 Correct 235 ms 34644 KB Output is correct
18 Correct 238 ms 35804 KB Output is correct
19 Correct 281 ms 38544 KB Output is correct
20 Correct 266 ms 37700 KB Output is correct
21 Correct 177 ms 35524 KB Output is correct
22 Correct 165 ms 35604 KB Output is correct
23 Correct 205 ms 35280 KB Output is correct
24 Correct 197 ms 35424 KB Output is correct
25 Correct 330 ms 38828 KB Output is correct
26 Correct 291 ms 33076 KB Output is correct
27 Correct 256 ms 32940 KB Output is correct
28 Correct 34 ms 20780 KB Output is correct
29 Correct 47 ms 21428 KB Output is correct
30 Correct 47 ms 21028 KB Output is correct
31 Correct 50 ms 21440 KB Output is correct
32 Correct 44 ms 20760 KB Output is correct
33 Correct 46 ms 20648 KB Output is correct
34 Correct 33 ms 20728 KB Output is correct
35 Correct 153 ms 35504 KB Output is correct
36 Correct 91 ms 33004 KB Output is correct
37 Correct 122 ms 33148 KB Output is correct
38 Correct 34 ms 20752 KB Output is correct
39 Correct 295 ms 41924 KB Output is correct
40 Correct 267 ms 42216 KB Output is correct
41 Correct 305 ms 41568 KB Output is correct
42 Correct 318 ms 41504 KB Output is correct
43 Correct 33 ms 20804 KB Output is correct
44 Correct 239 ms 35372 KB Output is correct
45 Correct 278 ms 34460 KB Output is correct
46 Correct 261 ms 35116 KB Output is correct
47 Correct 290 ms 35840 KB Output is correct
48 Correct 391 ms 37512 KB Output is correct
49 Correct 476 ms 37876 KB Output is correct
50 Correct 428 ms 37136 KB Output is correct
51 Correct 155 ms 33324 KB Output is correct
52 Correct 106 ms 33984 KB Output is correct
53 Correct 106 ms 33456 KB Output is correct
54 Correct 134 ms 34068 KB Output is correct
55 Correct 117 ms 32924 KB Output is correct
56 Correct 182 ms 34240 KB Output is correct
57 Correct 251 ms 36796 KB Output is correct
58 Correct 401 ms 33220 KB Output is correct
59 Correct 278 ms 32988 KB Output is correct