oj.uz

Submission #489278

# Submission time Handle Problem Language Result Execution time Memory
489278 2021-11-21T21:57:05 Z CSQ31 Inside information (BOI21_servers) C++17
60 / 100
 3500 ms 39756 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(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 11180 KB Output is correct
2 Correct 42 ms 11748 KB Output is correct
3 Correct 37 ms 11912 KB Output is correct
4 Correct 72 ms 11988 KB Output is correct
5 Correct 41 ms 12048 KB Output is correct
6 Correct 43 ms 11912 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11180 KB Output is correct
2 Correct 42 ms 11748 KB Output is correct
3 Correct 37 ms 11912 KB Output is correct
4 Correct 72 ms 11988 KB Output is correct
5 Correct 41 ms 12048 KB Output is correct
6 Correct 43 ms 11912 KB Output is correct
7 Correct 30 ms 11512 KB Output is correct
8 Correct 40 ms 12780 KB Output is correct
9 Incorrect 99 ms 12736 KB Extra information in the output file
10 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11328 KB Output is correct
2 Correct 199 ms 30412 KB Output is correct
3 Correct 187 ms 30172 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11328 KB Output is correct
2 Correct 199 ms 30412 KB Output is correct
3 Correct 187 ms 30172 KB Output is correct
4 Correct 28 ms 11588 KB Output is correct
5 Incorrect 3272 ms 31320 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11188 KB Output is correct
2 Correct 171 ms 37424 KB Output is correct
3 Correct 201 ms 37324 KB Output is correct
4 Correct 189 ms 37948 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11188 KB Output is correct
2 Correct 171 ms 37424 KB Output is correct
3 Correct 201 ms 37324 KB Output is correct
4 Correct 189 ms 37948 KB Output is correct
5 Correct 28 ms 11576 KB Output is correct
6 Correct 199 ms 39668 KB Output is correct
7 Execution timed out 3593 ms 39692 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11204 KB Output is correct
2 Correct 168 ms 29472 KB Output is correct
3 Correct 156 ms 29388 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11204 KB Output is correct
2 Correct 168 ms 29472 KB Output is correct
3 Correct 156 ms 29388 KB Output is correct
4 Correct 29 ms 11572 KB Output is correct
5 Correct 3434 ms 31880 KB Output is correct
6 Correct 168 ms 31044 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11288 KB Output is correct
2 Correct 169 ms 37316 KB Output is correct
3 Correct 171 ms 37316 KB Output is correct
4 Correct 170 ms 38024 KB Output is correct
5 Correct 29 ms 11264 KB Output is correct
6 Correct 165 ms 29452 KB Output is correct
7 Correct 152 ms 29380 KB Output is correct
8 Correct 250 ms 30020 KB Output is correct
9 Correct 206 ms 29740 KB Output is correct
10 Correct 261 ms 34636 KB Output is correct
11 Correct 333 ms 34044 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11288 KB Output is correct
2 Correct 169 ms 37316 KB Output is correct
3 Correct 171 ms 37316 KB Output is correct
4 Correct 170 ms 38024 KB Output is correct
5 Correct 29 ms 11264 KB Output is correct
6 Correct 165 ms 29452 KB Output is correct
7 Correct 152 ms 29380 KB Output is correct
8 Correct 250 ms 30020 KB Output is correct
9 Correct 206 ms 29740 KB Output is correct
10 Correct 261 ms 34636 KB Output is correct
11 Correct 333 ms 34044 KB Output is correct
12 Correct 29 ms 11464 KB Output is correct
13 Correct 210 ms 39664 KB Output is correct
14 Execution timed out 3578 ms 39756 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11212 KB Output is correct
2 Correct 43 ms 11844 KB Output is correct
3 Correct 37 ms 11924 KB Output is correct
4 Correct 53 ms 11952 KB Output is correct
5 Correct 48 ms 12280 KB Output is correct
6 Correct 44 ms 11980 KB Output is correct
7 Correct 28 ms 11268 KB Output is correct
8 Correct 173 ms 30264 KB Output is correct
9 Correct 172 ms 30208 KB Output is correct
10 Correct 31 ms 11292 KB Output is correct
11 Correct 168 ms 37296 KB Output is correct
12 Correct 173 ms 37328 KB Output is correct
13 Correct 167 ms 37896 KB Output is correct
14 Correct 29 ms 11304 KB Output is correct
15 Correct 173 ms 29428 KB Output is correct
16 Correct 153 ms 29364 KB Output is correct
17 Correct 236 ms 29756 KB Output is correct
18 Correct 211 ms 29772 KB Output is correct
19 Correct 270 ms 34568 KB Output is correct
20 Correct 329 ms 34060 KB Output is correct
21 Correct 180 ms 29828 KB Output is correct
22 Correct 192 ms 30092 KB Output is correct
23 Correct 208 ms 29420 KB Output is correct
24 Correct 196 ms 29404 KB Output is correct
25 Correct 260 ms 33876 KB Output is correct
26 Correct 242 ms 29148 KB Output is correct
27 Correct 229 ms 29232 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11212 KB Output is correct
2 Correct 43 ms 11844 KB Output is correct
3 Correct 37 ms 11924 KB Output is correct
4 Correct 53 ms 11952 KB Output is correct
5 Correct 48 ms 12280 KB Output is correct
6 Correct 44 ms 11980 KB Output is correct
7 Correct 28 ms 11268 KB Output is correct
8 Correct 173 ms 30264 KB Output is correct
9 Correct 172 ms 30208 KB Output is correct
10 Correct 31 ms 11292 KB Output is correct
11 Correct 168 ms 37296 KB Output is correct
12 Correct 173 ms 37328 KB Output is correct
13 Correct 167 ms 37896 KB Output is correct
14 Correct 29 ms 11304 KB Output is correct
15 Correct 173 ms 29428 KB Output is correct
16 Correct 153 ms 29364 KB Output is correct
17 Correct 236 ms 29756 KB Output is correct
18 Correct 211 ms 29772 KB Output is correct
19 Correct 270 ms 34568 KB Output is correct
20 Correct 329 ms 34060 KB Output is correct
21 Correct 180 ms 29828 KB Output is correct
22 Correct 192 ms 30092 KB Output is correct
23 Correct 208 ms 29420 KB Output is correct
24 Correct 196 ms 29404 KB Output is correct
25 Correct 260 ms 33876 KB Output is correct
26 Correct 242 ms 29148 KB Output is correct
27 Correct 229 ms 29232 KB Output is correct
28 Correct 31 ms 11456 KB Output is correct
29 Correct 39 ms 12740 KB Output is correct
30 Incorrect 90 ms 12752 KB Extra information in the output file
31 Halted 0 ms 0 KB -