oj.uz

Submission #489276

# Submission time Handle Problem Language Result Execution time Memory
489276 2021-11-21T21:54:24 Z CSQ31 Inside information (BOI21_servers) C++17
62.5 / 100
 3500 ms 39988 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]
	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(join[st[i]] <= tim)ans[tim]++;
		}
	}
	for(int tim : cq[v]){
		for(auto x:ed){
			ans[tim]+=(join[x] <= 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 33 ms 11248 KB Output is correct
2 Correct 44 ms 11836 KB Output is correct
3 Correct 36 ms 11884 KB Output is correct
4 Correct 53 ms 11924 KB Output is correct
5 Correct 41 ms 12104 KB Output is correct
6 Correct 36 ms 11968 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11248 KB Output is correct
2 Correct 44 ms 11836 KB Output is correct
3 Correct 36 ms 11884 KB Output is correct
4 Correct 53 ms 11924 KB Output is correct
5 Correct 41 ms 12104 KB Output is correct
6 Correct 36 ms 11968 KB Output is correct
7 Correct 31 ms 11600 KB Output is correct
8 Correct 42 ms 12904 KB Output is correct
9 Correct 76 ms 12860 KB Output is correct
10 Correct 45 ms 12868 KB Output is correct
11 Correct 39 ms 13152 KB Output is correct
12 Correct 306 ms 12848 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 11332 KB Output is correct
2 Correct 155 ms 30264 KB Output is correct
3 Correct 154 ms 30240 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 11332 KB Output is correct
2 Correct 155 ms 30264 KB Output is correct
3 Correct 154 ms 30240 KB Output is correct
4 Correct 29 ms 11616 KB Output is correct
5 Correct 2650 ms 31556 KB Output is correct
6 Execution timed out 3560 ms 32052 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11204 KB Output is correct
2 Correct 171 ms 37432 KB Output is correct
3 Correct 171 ms 37372 KB Output is correct
4 Correct 174 ms 38044 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11204 KB Output is correct
2 Correct 171 ms 37432 KB Output is correct
3 Correct 171 ms 37372 KB Output is correct
4 Correct 174 ms 38044 KB Output is correct
5 Correct 29 ms 11504 KB Output is correct
6 Correct 207 ms 39784 KB Output is correct
7 Execution timed out 3573 ms 39944 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 11208 KB Output is correct
2 Correct 165 ms 29504 KB Output is correct
3 Correct 157 ms 29652 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11208 KB Output is correct
2 Correct 165 ms 29504 KB Output is correct
3 Correct 157 ms 29652 KB Output is correct
4 Correct 33 ms 11528 KB Output is correct
5 Correct 3450 ms 32156 KB Output is correct
6 Correct 176 ms 33980 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11252 KB Output is correct
2 Correct 167 ms 37352 KB Output is correct
3 Correct 172 ms 37448 KB Output is correct
4 Correct 177 ms 38120 KB Output is correct
5 Correct 29 ms 11212 KB Output is correct
6 Correct 166 ms 29612 KB Output is correct
7 Correct 151 ms 29416 KB Output is correct
8 Correct 245 ms 29760 KB Output is correct
9 Correct 205 ms 29892 KB Output is correct
10 Correct 259 ms 34624 KB Output is correct
11 Correct 328 ms 34112 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11252 KB Output is correct
2 Correct 167 ms 37352 KB Output is correct
3 Correct 172 ms 37448 KB Output is correct
4 Correct 177 ms 38120 KB Output is correct
5 Correct 29 ms 11212 KB Output is correct
6 Correct 166 ms 29612 KB Output is correct
7 Correct 151 ms 29416 KB Output is correct
8 Correct 245 ms 29760 KB Output is correct
9 Correct 205 ms 29892 KB Output is correct
10 Correct 259 ms 34624 KB Output is correct
11 Correct 328 ms 34112 KB Output is correct
12 Correct 29 ms 11488 KB Output is correct
13 Correct 201 ms 39808 KB Output is correct
14 Execution timed out 3573 ms 39988 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 11272 KB Output is correct
2 Correct 43 ms 11792 KB Output is correct
3 Correct 36 ms 11972 KB Output is correct
4 Correct 53 ms 11912 KB Output is correct
5 Correct 44 ms 12060 KB Output is correct
6 Correct 35 ms 11972 KB Output is correct
7 Correct 32 ms 11328 KB Output is correct
8 Correct 150 ms 30252 KB Output is correct
9 Correct 176 ms 30296 KB Output is correct
10 Correct 35 ms 11332 KB Output is correct
11 Correct 202 ms 37388 KB Output is correct
12 Correct 169 ms 37392 KB Output is correct
13 Correct 169 ms 38032 KB Output is correct
14 Correct 31 ms 11244 KB Output is correct
15 Correct 164 ms 29612 KB Output is correct
16 Correct 153 ms 29452 KB Output is correct
17 Correct 231 ms 29764 KB Output is correct
18 Correct 207 ms 29888 KB Output is correct
19 Correct 257 ms 34676 KB Output is correct
20 Correct 321 ms 34144 KB Output is correct
21 Correct 166 ms 29880 KB Output is correct
22 Correct 165 ms 30236 KB Output is correct
23 Correct 189 ms 29504 KB Output is correct
24 Correct 188 ms 29508 KB Output is correct
25 Correct 268 ms 34020 KB Output is correct
26 Correct 226 ms 29276 KB Output is correct
27 Correct 228 ms 29376 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 11272 KB Output is correct
2 Correct 43 ms 11792 KB Output is correct
3 Correct 36 ms 11972 KB Output is correct
4 Correct 53 ms 11912 KB Output is correct
5 Correct 44 ms 12060 KB Output is correct
6 Correct 35 ms 11972 KB Output is correct
7 Correct 32 ms 11328 KB Output is correct
8 Correct 150 ms 30252 KB Output is correct
9 Correct 176 ms 30296 KB Output is correct
10 Correct 35 ms 11332 KB Output is correct
11 Correct 202 ms 37388 KB Output is correct
12 Correct 169 ms 37392 KB Output is correct
13 Correct 169 ms 38032 KB Output is correct
14 Correct 31 ms 11244 KB Output is correct
15 Correct 164 ms 29612 KB Output is correct
16 Correct 153 ms 29452 KB Output is correct
17 Correct 231 ms 29764 KB Output is correct
18 Correct 207 ms 29888 KB Output is correct
19 Correct 257 ms 34676 KB Output is correct
20 Correct 321 ms 34144 KB Output is correct
21 Correct 166 ms 29880 KB Output is correct
22 Correct 165 ms 30236 KB Output is correct
23 Correct 189 ms 29504 KB Output is correct
24 Correct 188 ms 29508 KB Output is correct
25 Correct 268 ms 34020 KB Output is correct
26 Correct 226 ms 29276 KB Output is correct
27 Correct 228 ms 29376 KB Output is correct
28 Correct 31 ms 11548 KB Output is correct
29 Correct 43 ms 12804 KB Output is correct
30 Correct 74 ms 12864 KB Output is correct
31 Correct 46 ms 12952 KB Output is correct
32 Correct 39 ms 13128 KB Output is correct
33 Correct 304 ms 12888 KB Output is correct
34 Correct 29 ms 11724 KB Output is correct
35 Correct 3374 ms 31480 KB Output is correct
36 Execution timed out 3591 ms 32012 KB Time limit exceeded
37 Halted 0 ms 0 KB -