oj.uz

Submission #489279

# Submission time Handle Problem Language Result Execution time Memory
489279 2021-11-21T21:59:16 Z CSQ31 Inside information (BOI21_servers) C++17
62.5 / 100
 3500 ms 39972 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define all(a) a.begin(),a.end()
typedef pair<int,int> pii;
const int MAXN = 2e5;
vector<pii>adj[MAXN];
int dep[MAXN],par[18][MAXN],asc[MAXN],dsc[MAXN],val[MAXN],n,k;
char c[250000];
int a[250000],d[250000],ans[250000];
void dfs0(int v,int u,int ww){
	for(int i=1;i<=17;i++)par[i][v] = par[i-1][par[i-1][v]];
	for(pii z:adj[v]){
		int x = z.fi;
		int w = z.se;
		if(x == u)continue;
		val[x] = w;
		asc[x] = dsc[x] = dep[v];
		if(w > ww || v==1)asc[x] = asc[v];	
		if(w < ww || v==1)dsc[x] = dsc[v];
		
		dep[x] = dep[v]+1;
		par[0][x] = v;
		dfs0(x,v,w);
	}
}
int jump(int v,int d){
	for(int i=0;i<=17 && d;i++){
		if(d&1)v=par[i][v];
		d/=2;
	}
	return v;
}
int lca(int v,int u){
	if(dep[v] < dep[u])swap(v,u);
	v = jump(v,dep[v] - dep[u]);
	
	if(v==u)return v;
	for(int i=17;i>=0;i--){
		if(par[i][v] != par[i][u]){
			v = par[i][v];
			u = par[i][u];
		}
	}
	return par[0][v];
}
//want to count number of paths from i to j
//such that i->j is increasing
//and the last edge that touches j is <= t
//let c be the centroid
//call node x a start node if c->x is increasing
//call node x an end node if c->x is decreasing 

//can sweepline on their time but overcounting????
//call the join time of node x the time where x is first connected to c
//the add time of end node x the time where the first edge from path c->i is added
//contribution for start node i is number of end nodes with join time > its join time and add time <= t
//ok so sweepline backwards by join time then pick whatever sum aggre ds,fenwick should be fast enough 
vector<int>cq[MAXN];
int sub[MAXN],join[MAXN],reach[MAXN],fen[250000];
bool ded[MAXN];
void upd(int i,int x){
	for(;i<=240000;i+=i&(-i))fen[i]+=x;
}
int query(int i){
	int res = 0;
	for(;i;i-=i&(-i))res+=fen[i];
	return res;
}
void get(int v,int u){
	sub[v] = 1;
	for(auto x:adj[v]){
		if(x.fi==u ||ded[x.fi])continue;
		get(x.fi,v);
		sub[v]+=sub[x.fi];
	}
}
int cen(int v,int u,int n){
	for(auto x:adj[v]){
		if(ded[x.fi] || x.fi == u)continue;
		if(sub[x.fi] > n/2)return cen(x.fi,v,n);
	}
	return v;
}
vector<int>st,ed;
void dfs(int v,int u,int type,int ww){ //type 1 increasing,type 2 decreasing
	if(type<=1)st.pb(v);
	if(type!=1)ed.pb(v);
	
	join[v] = max(join[u],ww);
	reach[v] = min(reach[u],ww);
	for(pii z:adj[v]){
		int x = z.fi;
		int w = z.se;
		if(x==u || ded[x])continue;
		if((!type || type ==1) && ww > w)dfs(x,v,1,w);
		if((!type || type ==2) && ww < w)dfs(x,v,2,w);
	}
	
}
void solve(int v){
	get(v,0);
	v = cen(v,0,sub[v]);
	ded[v] = 1;
	join[v] = 0;
	reach[v] = 1e9;
	for(auto z:adj[v]){
		int x = z.fi;
		int w = z.se;
		if(ded[x])continue;
		dfs(x,v,0,w);
	}
	//for a st node i,want number of ed nodes j st reach[j] > join[i] and join[j] <= current ime
	//first ineq eliminate by sweep line
	//second ineq can eliminate by [insert ds]
	st.pb(v);
	join[v]=-1;
	sort(all(st),[&](int i,int j){return join[i] > join[j];});
	sort(all(ed),[&](int i,int j){return reach[i] > reach[j];});
	
	int ptr = 0;
	for(int i=0;i<sz(st);i++){
		while(ptr<sz(ed) && reach[ed[ptr]] > join[st[i]])ptr++;
		for(int tim : cq[st[i]]){
			for(int j=0;j<ptr;j++){
				if(join[ed[j]] <= tim)ans[tim]++;
			}
			if(st[i]!=v && join[st[i]] <= tim)ans[tim]++;
		}
	}
	st.clear();
	ed.clear();
	for(auto z:adj[v])if(!ded[z.fi])solve(z.fi);
}
int main()
{
	owo
	cin>>n>>k;
	for(int i=0;i<n+k-1;i++){
		cin>>c[i]>>a[i];
		if(c[i]!='C')cin>>d[i];
		if(c[i] == 'S'){
			adj[a[i]].pb({d[i],i});
			adj[d[i]].pb({a[i],i});
		}
		if(c[i]=='C')cq[a[i]].pb(i);
	}
	dfs0(1,0,0);
	solve(1);
	for(int i=0;i<n+k-1;i++){
		if(c[i]=='C')cout<<ans[i]+1<<'\n';
		else if(c[i]=='Q'){ //this solves for Q queries now for C queries
			int v = a[i];
			int u = d[i];

			int m = lca(v,u),last = -1e9;
			if(v!=m)last = val[v];
			else if(u!=m)last = val[jump(u,dep[u]-dep[m]-1)];
			bool ok= (last<=i);
			
			if(asc[v] > dep[m] || dsc[u] > dep[m])ok = 0;
			if(v!=m && u!= m){
				v = jump(v,dep[v]-dep[m]-1);
				u = jump(u,dep[u]-dep[m]-1);
				if(val[u] > val[v])ok = 0;
			}
			if(ok)cout<<"yes"<<'\n';
			else cout<<"no"<<'\n';
		}
		
	}
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11212 KB Output is correct
2 Correct 44 ms 11776 KB Output is correct
3 Correct 38 ms 11928 KB Output is correct
4 Correct 65 ms 11976 KB Output is correct
5 Correct 53 ms 12100 KB Output is correct
6 Correct 36 ms 11972 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11212 KB Output is correct
2 Correct 44 ms 11776 KB Output is correct
3 Correct 38 ms 11928 KB Output is correct
4 Correct 65 ms 11976 KB Output is correct
5 Correct 53 ms 12100 KB Output is correct
6 Correct 36 ms 11972 KB Output is correct
7 Correct 31 ms 11460 KB Output is correct
8 Correct 40 ms 12776 KB Output is correct
9 Correct 97 ms 12780 KB Output is correct
10 Correct 52 ms 12740 KB Output is correct
11 Correct 39 ms 12964 KB Output is correct
12 Correct 330 ms 12712 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 11216 KB Output is correct
2 Correct 185 ms 30172 KB Output is correct
3 Correct 201 ms 30180 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 11216 KB Output is correct
2 Correct 185 ms 30172 KB Output is correct
3 Correct 201 ms 30180 KB Output is correct
4 Correct 29 ms 11604 KB Output is correct
5 Correct 3327 ms 31368 KB Output is correct
6 Execution timed out 3570 ms 30480 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11212 KB Output is correct
2 Correct 194 ms 37552 KB Output is correct
3 Correct 174 ms 37376 KB Output is correct
4 Correct 171 ms 37952 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11212 KB Output is correct
2 Correct 194 ms 37552 KB Output is correct
3 Correct 174 ms 37376 KB Output is correct
4 Correct 171 ms 37952 KB Output is correct
5 Correct 38 ms 11520 KB Output is correct
6 Correct 227 ms 39784 KB Output is correct
7 Execution timed out 3562 ms 39832 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11212 KB Output is correct
2 Correct 190 ms 29488 KB Output is correct
3 Correct 152 ms 29396 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11212 KB Output is correct
2 Correct 190 ms 29488 KB Output is correct
3 Correct 152 ms 29396 KB Output is correct
4 Correct 29 ms 11484 KB Output is correct
5 Correct 3493 ms 31932 KB Output is correct
6 Correct 188 ms 31048 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11252 KB Output is correct
2 Correct 174 ms 37348 KB Output is correct
3 Correct 200 ms 37288 KB Output is correct
4 Correct 182 ms 37932 KB Output is correct
5 Correct 29 ms 11208 KB Output is correct
6 Correct 174 ms 29420 KB Output is correct
7 Correct 156 ms 29300 KB Output is correct
8 Correct 234 ms 29704 KB Output is correct
9 Correct 224 ms 29896 KB Output is correct
10 Correct 262 ms 34612 KB Output is correct
11 Correct 316 ms 33912 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11252 KB Output is correct
2 Correct 174 ms 37348 KB Output is correct
3 Correct 200 ms 37288 KB Output is correct
4 Correct 182 ms 37932 KB Output is correct
5 Correct 29 ms 11208 KB Output is correct
6 Correct 174 ms 29420 KB Output is correct
7 Correct 156 ms 29300 KB Output is correct
8 Correct 234 ms 29704 KB Output is correct
9 Correct 224 ms 29896 KB Output is correct
10 Correct 262 ms 34612 KB Output is correct
11 Correct 316 ms 33912 KB Output is correct
12 Correct 28 ms 11468 KB Output is correct
13 Correct 235 ms 39684 KB Output is correct
14 Execution timed out 3577 ms 39972 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 11192 KB Output is correct
2 Correct 44 ms 11844 KB Output is correct
3 Correct 37 ms 11944 KB Output is correct
4 Correct 53 ms 11884 KB Output is correct
5 Correct 41 ms 12108 KB Output is correct
6 Correct 35 ms 11904 KB Output is correct
7 Correct 28 ms 11256 KB Output is correct
8 Correct 173 ms 30188 KB Output is correct
9 Correct 170 ms 30252 KB Output is correct
10 Correct 28 ms 11212 KB Output is correct
11 Correct 168 ms 37368 KB Output is correct
12 Correct 176 ms 37460 KB Output is correct
13 Correct 168 ms 37988 KB Output is correct
14 Correct 29 ms 11200 KB Output is correct
15 Correct 164 ms 29500 KB Output is correct
16 Correct 159 ms 29380 KB Output is correct
17 Correct 234 ms 29708 KB Output is correct
18 Correct 205 ms 29792 KB Output is correct
19 Correct 267 ms 34624 KB Output is correct
20 Correct 349 ms 33936 KB Output is correct
21 Correct 180 ms 29796 KB Output is correct
22 Correct 195 ms 30124 KB Output is correct
23 Correct 196 ms 29320 KB Output is correct
24 Correct 196 ms 29380 KB Output is correct
25 Correct 265 ms 33868 KB Output is correct
26 Correct 226 ms 29104 KB Output is correct
27 Correct 237 ms 29240 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 11192 KB Output is correct
2 Correct 44 ms 11844 KB Output is correct
3 Correct 37 ms 11944 KB Output is correct
4 Correct 53 ms 11884 KB Output is correct
5 Correct 41 ms 12108 KB Output is correct
6 Correct 35 ms 11904 KB Output is correct
7 Correct 28 ms 11256 KB Output is correct
8 Correct 173 ms 30188 KB Output is correct
9 Correct 170 ms 30252 KB Output is correct
10 Correct 28 ms 11212 KB Output is correct
11 Correct 168 ms 37368 KB Output is correct
12 Correct 176 ms 37460 KB Output is correct
13 Correct 168 ms 37988 KB Output is correct
14 Correct 29 ms 11200 KB Output is correct
15 Correct 164 ms 29500 KB Output is correct
16 Correct 159 ms 29380 KB Output is correct
17 Correct 234 ms 29708 KB Output is correct
18 Correct 205 ms 29792 KB Output is correct
19 Correct 267 ms 34624 KB Output is correct
20 Correct 349 ms 33936 KB Output is correct
21 Correct 180 ms 29796 KB Output is correct
22 Correct 195 ms 30124 KB Output is correct
23 Correct 196 ms 29320 KB Output is correct
24 Correct 196 ms 29380 KB Output is correct
25 Correct 265 ms 33868 KB Output is correct
26 Correct 226 ms 29104 KB Output is correct
27 Correct 237 ms 29240 KB Output is correct
28 Correct 30 ms 11476 KB Output is correct
29 Correct 40 ms 12644 KB Output is correct
30 Correct 90 ms 12696 KB Output is correct
31 Correct 47 ms 12740 KB Output is correct
32 Correct 38 ms 12984 KB Output is correct
33 Correct 333 ms 12748 KB Output is correct
34 Correct 28 ms 11588 KB Output is correct
35 Correct 2966 ms 31332 KB Output is correct
36 Execution timed out 3575 ms 30484 KB Time limit exceeded
37 Halted 0 ms 0 KB -