oj.uz

Submission #489277

# Submission time Handle Problem Language Result Execution time Memory
489277 2021-11-21T21:55:10 Z CSQ31 Inside information (BOI21_servers) C++17
50 / 100
 347 ms 38052 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);
	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]++;
		}
	}
	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 31 ms 11176 KB Output is correct
2 Correct 43 ms 11756 KB Output is correct
3 Correct 37 ms 11948 KB Output is correct
4 Correct 53 ms 11864 KB Output is correct
5 Correct 41 ms 12100 KB Output is correct
6 Correct 35 ms 11908 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 11176 KB Output is correct
2 Correct 43 ms 11756 KB Output is correct
3 Correct 37 ms 11948 KB Output is correct
4 Correct 53 ms 11864 KB Output is correct
5 Correct 41 ms 12100 KB Output is correct
6 Correct 35 ms 11908 KB Output is correct
7 Incorrect 31 ms 11536 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11212 KB Output is correct
2 Correct 180 ms 30396 KB Output is correct
3 Correct 172 ms 30160 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11212 KB Output is correct
2 Correct 180 ms 30396 KB Output is correct
3 Correct 172 ms 30160 KB Output is correct
4 Incorrect 29 ms 11564 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11288 KB Output is correct
2 Correct 173 ms 37300 KB Output is correct
3 Correct 176 ms 37368 KB Output is correct
4 Correct 171 ms 37980 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11288 KB Output is correct
2 Correct 173 ms 37300 KB Output is correct
3 Correct 176 ms 37368 KB Output is correct
4 Correct 171 ms 37980 KB Output is correct
5 Incorrect 29 ms 11548 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11228 KB Output is correct
2 Correct 177 ms 29572 KB Output is correct
3 Correct 151 ms 29380 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11228 KB Output is correct
2 Correct 177 ms 29572 KB Output is correct
3 Correct 151 ms 29380 KB Output is correct
4 Incorrect 31 ms 11500 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11292 KB Output is correct
2 Correct 181 ms 37332 KB Output is correct
3 Correct 166 ms 37304 KB Output is correct
4 Correct 172 ms 37884 KB Output is correct
5 Correct 29 ms 11204 KB Output is correct
6 Correct 164 ms 29512 KB Output is correct
7 Correct 157 ms 29324 KB Output is correct
8 Correct 244 ms 29668 KB Output is correct
9 Correct 210 ms 29728 KB Output is correct
10 Correct 264 ms 34704 KB Output is correct
11 Correct 319 ms 33860 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11292 KB Output is correct
2 Correct 181 ms 37332 KB Output is correct
3 Correct 166 ms 37304 KB Output is correct
4 Correct 172 ms 37884 KB Output is correct
5 Correct 29 ms 11204 KB Output is correct
6 Correct 164 ms 29512 KB Output is correct
7 Correct 157 ms 29324 KB Output is correct
8 Correct 244 ms 29668 KB Output is correct
9 Correct 210 ms 29728 KB Output is correct
10 Correct 264 ms 34704 KB Output is correct
11 Correct 319 ms 33860 KB Output is correct
12 Incorrect 29 ms 11548 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11460 KB Output is correct
2 Correct 44 ms 11764 KB Output is correct
3 Correct 37 ms 11964 KB Output is correct
4 Correct 55 ms 11968 KB Output is correct
5 Correct 41 ms 12144 KB Output is correct
6 Correct 36 ms 11944 KB Output is correct
7 Correct 29 ms 11240 KB Output is correct
8 Correct 175 ms 30232 KB Output is correct
9 Correct 177 ms 30232 KB Output is correct
10 Correct 28 ms 11292 KB Output is correct
11 Correct 171 ms 37284 KB Output is correct
12 Correct 167 ms 37352 KB Output is correct
13 Correct 174 ms 38052 KB Output is correct
14 Correct 30 ms 11212 KB Output is correct
15 Correct 164 ms 29516 KB Output is correct
16 Correct 154 ms 29400 KB Output is correct
17 Correct 244 ms 29716 KB Output is correct
18 Correct 204 ms 29720 KB Output is correct
19 Correct 263 ms 34544 KB Output is correct
20 Correct 347 ms 33840 KB Output is correct
21 Correct 181 ms 29788 KB Output is correct
22 Correct 194 ms 30152 KB Output is correct
23 Correct 216 ms 29380 KB Output is correct
24 Correct 197 ms 29368 KB Output is correct
25 Correct 259 ms 33852 KB Output is correct
26 Correct 231 ms 29216 KB Output is correct
27 Correct 228 ms 29228 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11460 KB Output is correct
2 Correct 44 ms 11764 KB Output is correct
3 Correct 37 ms 11964 KB Output is correct
4 Correct 55 ms 11968 KB Output is correct
5 Correct 41 ms 12144 KB Output is correct
6 Correct 36 ms 11944 KB Output is correct
7 Correct 29 ms 11240 KB Output is correct
8 Correct 175 ms 30232 KB Output is correct
9 Correct 177 ms 30232 KB Output is correct
10 Correct 28 ms 11292 KB Output is correct
11 Correct 171 ms 37284 KB Output is correct
12 Correct 167 ms 37352 KB Output is correct
13 Correct 174 ms 38052 KB Output is correct
14 Correct 30 ms 11212 KB Output is correct
15 Correct 164 ms 29516 KB Output is correct
16 Correct 154 ms 29400 KB Output is correct
17 Correct 244 ms 29716 KB Output is correct
18 Correct 204 ms 29720 KB Output is correct
19 Correct 263 ms 34544 KB Output is correct
20 Correct 347 ms 33840 KB Output is correct
21 Correct 181 ms 29788 KB Output is correct
22 Correct 194 ms 30152 KB Output is correct
23 Correct 216 ms 29380 KB Output is correct
24 Correct 197 ms 29368 KB Output is correct
25 Correct 259 ms 33852 KB Output is correct
26 Correct 231 ms 29216 KB Output is correct
27 Correct 228 ms 29228 KB Output is correct
28 Incorrect 32 ms 11476 KB Extra information in the output file
29 Halted 0 ms 0 KB -