oj.uz

Submission #489271

# Submission time Handle Problem Language Result Execution time Memory
489271 2021-11-21T21:30:15 Z CSQ31 Inside information (BOI21_servers) C++17
52.5 / 100
 3500 ms 42732 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);
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];
bool ded[MAXN];
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<pii>ver;
void dfs(int v,int u,int type,int ww){ //type 1 increasing,type 2 decreasing
	ver.pb({v,type});
	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);
	//cout<<v<<" ";
	v = cen(v,0,sub[v]);
	ded[v] = 1;
    //cout<<v<<'\n';
	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(auto x:ver)cout<<"("<<x.fi<<" "<<x.se<<" "<<join[x.fi]<<")"<<'\n';
	sort(ver.begin(),ver.end(),[&](pii i,pii j){return join[i.fi] > join[j.fi];});
	int m = sz(ver);
	for(int i=0;i<m;i++){
		int x = ver[i].fi;
		int t = ver[i].se;
		if(t<=1){
			for(int tim : cq[x]){
				for(int j=0;j<i;j++){
					int y = ver[j].fi;
					if(ver[j].se != 1 && reach[y] > join[x] && join[y] <= tim)ans[tim]++;
				}
				if(join[x] <= tim)ans[tim]++;
			}
		}
		if(t!=1){
			for(int tim : cq[v]){
				if(join[x] <= tim)ans[tim]++;
			}
		}
	}
	ver.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 31 ms 11204 KB Output is correct
2 Correct 46 ms 11776 KB Output is correct
3 Correct 38 ms 11964 KB Output is correct
4 Correct 54 ms 11968 KB Output is correct
5 Correct 42 ms 12092 KB Output is correct
6 Correct 35 ms 11964 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 11204 KB Output is correct
2 Correct 46 ms 11776 KB Output is correct
3 Correct 38 ms 11964 KB Output is correct
4 Correct 54 ms 11968 KB Output is correct
5 Correct 42 ms 12092 KB Output is correct
6 Correct 35 ms 11964 KB Output is correct
7 Correct 31 ms 11588 KB Output is correct
8 Correct 42 ms 13464 KB Output is correct
9 Correct 153 ms 13852 KB Output is correct
10 Correct 47 ms 13844 KB Output is correct
11 Correct 39 ms 14080 KB Output is correct
12 Correct 388 ms 13824 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11204 KB Output is correct
2 Correct 147 ms 29976 KB Output is correct
3 Correct 162 ms 30012 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11204 KB Output is correct
2 Correct 147 ms 29976 KB Output is correct
3 Correct 162 ms 30012 KB Output is correct
4 Correct 36 ms 11564 KB Output is correct
5 Execution timed out 3596 ms 33244 KB Time limit exceeded
6 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 179 ms 37356 KB Output is correct
3 Correct 188 ms 37336 KB Output is correct
4 Correct 178 ms 38448 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 179 ms 37356 KB Output is correct
3 Correct 188 ms 37336 KB Output is correct
4 Correct 178 ms 38448 KB Output is correct
5 Correct 29 ms 11588 KB Output is correct
6 Correct 215 ms 42604 KB Output is correct
7 Execution timed out 3587 ms 42732 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11212 KB Output is correct
2 Correct 200 ms 30036 KB Output is correct
3 Correct 167 ms 29388 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11212 KB Output is correct
2 Correct 200 ms 30036 KB Output is correct
3 Correct 167 ms 29388 KB Output is correct
4 Correct 32 ms 11592 KB Output is correct
5 Execution timed out 3592 ms 34556 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11212 KB Output is correct
2 Correct 211 ms 37316 KB Output is correct
3 Correct 169 ms 37376 KB Output is correct
4 Correct 180 ms 38492 KB Output is correct
5 Correct 30 ms 11248 KB Output is correct
6 Correct 182 ms 29936 KB Output is correct
7 Correct 153 ms 29384 KB Output is correct
8 Correct 255 ms 29708 KB Output is correct
9 Correct 203 ms 29776 KB Output is correct
10 Correct 277 ms 34812 KB Output is correct
11 Correct 344 ms 34132 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11212 KB Output is correct
2 Correct 211 ms 37316 KB Output is correct
3 Correct 169 ms 37376 KB Output is correct
4 Correct 180 ms 38492 KB Output is correct
5 Correct 30 ms 11248 KB Output is correct
6 Correct 182 ms 29936 KB Output is correct
7 Correct 153 ms 29384 KB Output is correct
8 Correct 255 ms 29708 KB Output is correct
9 Correct 203 ms 29776 KB Output is correct
10 Correct 277 ms 34812 KB Output is correct
11 Correct 344 ms 34132 KB Output is correct
12 Correct 32 ms 11584 KB Output is correct
13 Correct 248 ms 42568 KB Output is correct
14 Execution timed out 3595 ms 42728 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 11232 KB Output is correct
2 Correct 44 ms 11848 KB Output is correct
3 Correct 37 ms 11840 KB Output is correct
4 Correct 56 ms 11976 KB Output is correct
5 Correct 46 ms 12100 KB Output is correct
6 Correct 34 ms 11928 KB Output is correct
7 Correct 27 ms 11316 KB Output is correct
8 Correct 146 ms 30052 KB Output is correct
9 Correct 145 ms 29996 KB Output is correct
10 Correct 29 ms 11280 KB Output is correct
11 Correct 176 ms 37368 KB Output is correct
12 Correct 192 ms 37380 KB Output is correct
13 Correct 176 ms 38452 KB Output is correct
14 Correct 29 ms 11180 KB Output is correct
15 Correct 196 ms 29928 KB Output is correct
16 Correct 156 ms 29340 KB Output is correct
17 Correct 256 ms 29716 KB Output is correct
18 Correct 228 ms 29868 KB Output is correct
19 Correct 261 ms 34820 KB Output is correct
20 Correct 330 ms 34184 KB Output is correct
21 Correct 166 ms 29912 KB Output is correct
22 Correct 196 ms 30004 KB Output is correct
23 Correct 179 ms 29356 KB Output is correct
24 Correct 198 ms 29516 KB Output is correct
25 Correct 311 ms 33732 KB Output is correct
26 Correct 242 ms 29384 KB Output is correct
27 Correct 281 ms 29544 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 11232 KB Output is correct
2 Correct 44 ms 11848 KB Output is correct
3 Correct 37 ms 11840 KB Output is correct
4 Correct 56 ms 11976 KB Output is correct
5 Correct 46 ms 12100 KB Output is correct
6 Correct 34 ms 11928 KB Output is correct
7 Correct 27 ms 11316 KB Output is correct
8 Correct 146 ms 30052 KB Output is correct
9 Correct 145 ms 29996 KB Output is correct
10 Correct 29 ms 11280 KB Output is correct
11 Correct 176 ms 37368 KB Output is correct
12 Correct 192 ms 37380 KB Output is correct
13 Correct 176 ms 38452 KB Output is correct
14 Correct 29 ms 11180 KB Output is correct
15 Correct 196 ms 29928 KB Output is correct
16 Correct 156 ms 29340 KB Output is correct
17 Correct 256 ms 29716 KB Output is correct
18 Correct 228 ms 29868 KB Output is correct
19 Correct 261 ms 34820 KB Output is correct
20 Correct 330 ms 34184 KB Output is correct
21 Correct 166 ms 29912 KB Output is correct
22 Correct 196 ms 30004 KB Output is correct
23 Correct 179 ms 29356 KB Output is correct
24 Correct 198 ms 29516 KB Output is correct
25 Correct 311 ms 33732 KB Output is correct
26 Correct 242 ms 29384 KB Output is correct
27 Correct 281 ms 29544 KB Output is correct
28 Correct 31 ms 11544 KB Output is correct
29 Correct 41 ms 13880 KB Output is correct
30 Correct 166 ms 13812 KB Output is correct
31 Correct 49 ms 14000 KB Output is correct
32 Correct 38 ms 14140 KB Output is correct
33 Correct 390 ms 13832 KB Output is correct
34 Correct 28 ms 12420 KB Output is correct
35 Execution timed out 3577 ms 33204 KB Time limit exceeded
36 Halted 0 ms 0 KB -