oj.uz

Submission #963974

# Submission time Handle Problem Language Result Execution time Memory
963974 2024-04-16T06:12:56 Z pcc Inside information (BOI21_servers) C++17
100 / 100
 411 ms 53764 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define tiii tuple<int,int,int>

const int mxn = 3e5+10;
vector<pii> tree[mxn];
int N,Q;
vector<tiii> req,req2;
int ans[mxn];
int isask[mxn];

namespace HLD{
	int sz[mxn],idx[mxn],link_top[mxn],par[mxn],bs[mxn],dep[mxn],cnt,val[mxn];
	struct node{
		bool inc,dec;
		int mx,mn;
		node(){
			inc = dec = 1;
			mx = mn = 0;
		}
	};
	node pull(node a,node b){
		node re;
		if(a.mx == -1)return b;
		if(b.mx == -1)return a;
		re.inc = a.inc&&b.inc&&(a.mx<=b.mn);
		re.dec = a.dec&&b.dec&&(a.mn>=b.mx);
		re.mx = max(a.mx,b.mx);
		re.mn = min(a.mn,b.mn);
		return re;
	}

	struct SEG{
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
		node seg[mxn*4];
		void build(int now,int l,int r){
			if(l == r){
				seg[now].mx = seg[now].mn = val[l];
				seg[now].dec = seg[now].inc = 1;
				return;
			}
			build(ls,l,mid);
			build(rs,mid+1,r);
			seg[now] = pull(seg[ls],seg[rs]);
			return;
		}
		node getval(int now,int l,int r,int s,int e){
			assert(s<=e);
			if(l>=s&&e>=r)return seg[now];
			if(mid>=e)return getval(ls,l,mid,s,e);
			else if(mid<s)return getval(rs,mid+1,r,s,e);
			else return pull(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
		}
#undef ls
#undef rs
#undef mid
	};

	SEG seg;
	void dfs(int now){
		sz[now] = 1;
		for(auto nxt:tree[now]){
			if(nxt.fs == par[now])continue;
			par[nxt.fs] = now;
			dep[nxt.fs] = dep[now]+1;
			dfs(nxt.fs);
			sz[now] += sz[nxt.fs];
			if(!bs[now]||sz[bs[now]]<=sz[nxt.fs])bs[now] = nxt.fs;
		}
		return;
	}
	void dfs2(int now,int top){
		link_top[now] = top;
		idx[now] = ++cnt;
		if(bs[now])dfs2(bs[now],top);
		for(auto nxt:tree[now]){
			if(nxt.fs == par[now])continue;
			if(nxt.fs != bs[now])dfs2(nxt.fs,nxt.fs);
			val[idx[nxt.fs]] = nxt.sc;
		}
		return;
	}
	void GO(){
		dfs(1);
		dfs2(1,1);
		seg.build(0,1,N);
	}
	node LCA(int a,int b){
		int ta = link_top[a],tb = link_top[b];
		node lv,rv;
		lv.mx = lv.mn = rv.mx = rv.mn = -1;
		while(ta != tb){
			if(dep[ta]>dep[tb]){
				lv = pull(seg.getval(0,1,N,idx[ta],idx[a]),lv);
				a = par[ta];
				ta = link_top[a];
			}
			else{
				rv = pull(seg.getval(0,1,N,idx[tb],idx[b]),rv);
				b = par[tb];
				tb = link_top[b];
			}
		}
		if(dep[a]>dep[b]){
			lv = pull(seg.getval(0,1,N,idx[b]+1,idx[a]),lv);
		}
		else if(dep[a]<dep[b]){
			rv = pull(seg.getval(0,1,N,idx[a]+1,idx[b]),rv);
		}
		//cout<<lv.mx<<' '<<lv.mn<<' '<<lv.dec<<' '<<lv.inc<<';'<<rv.mx<<' '<<rv.mn<<' '<<rv.dec<<' '<<rv.inc<<endl;
		swap(rv.inc,rv.dec);
		return pull(rv,lv);
	}
}

namespace CD{
	struct BIT{
		int bit[mxn];
		void modify(int p,int v){
			for(;p<mxn;p+=p&-p)bit[p] += v;
			return;
		}
		int getval(int s,int e){
			int re = 0;
			for(;e>0;e-= e&-e)re += bit[e];
			s--;
			for(;s>0;s-= s&-s)re -= bit[s];
			return re;
		}
		BIT(){
			memset(bit,0,sizeof(bit));
		}
	};
	BIT bit;
	int sz[mxn];
	bitset<mxn> del;
	vector<int> ask[mxn];

	int szdfs(int now,int par){
		sz[now] = 1;
		for(auto [nxt,w]:tree[now]){
			if(del[nxt]||nxt == par)continue;
			sz[now] += szdfs(nxt,now);
		}
		return sz[now];
	}
	int find_centroid(int now,int par,int tar){
		for(auto [nxt,w]:tree[now]){
			if(del[nxt]||nxt == par)continue;
			if(sz[nxt]>tar)return find_centroid(nxt,now,tar);
		}
		return now;
	}

	void dfs1(int now,int par,int mx,int mn){
		for(auto &i:ask[now]){
			if(i<mx)continue;
			ans[i] += bit.getval(mx,i);
		}
		for(auto [nxt,w]:tree[now]){
			if(nxt == par||del[nxt]||mn<w)continue;
			dfs1(nxt,now,mx,w);
		}
		return;
	}

	void dfs2(int now,int par,int mx,int mn){
		bit.modify(mx,1);
		for(auto [nxt,w]:tree[now]){
			if(nxt == par||del[nxt]||mx>w)continue;
			dfs2(nxt,now,w,mn);
		}
		return;
	}

	void dfs3(int now,int par){
		for(auto [nxt,w]:tree[now]){
			if(nxt == par||del[nxt])continue;
			bit.modify(w,-bit.getval(w,w));
			dfs3(nxt,now);
		}
		return;
	}

	void cendfs(int now){
		now = find_centroid(now,now,(szdfs(now,now)-1)>>1);
		for(auto [nxt,w]:tree[now]){
			if(del[nxt])continue;
			bit.modify(w,1);
			dfs1(nxt,now,w,w);
			dfs2(nxt,now,w,w);
			bit.modify(w,-1);
		}
		for(auto &i:ask[now]){
			ans[i] += bit.getval(0,i);
		}
		del[now] = true;
		dfs3(now,now);
		for(auto [nxt,w]:tree[now]){
			if(!del[nxt])cendfs(nxt);
		}
		return;
	}

	void GO(){
		for(auto &[id,pt,__]:req2){
			ask[pt].push_back(id);
		}
		for(int i = 1;i<=N;i++)sort(tree[i].begin(),tree[i].end(),[](pii a,pii b){return a.sc>b.sc;});
		cendfs(1);
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 1;i<N+Q;i++){
		char c;
		cin>>c;
		if(c == 'S'){
			int a,b;
			cin>>a>>b;
			tree[a].push_back(pii(b,i));
			tree[b].push_back(pii(a,i));
		}
		else if(c == 'Q'){
			isask[i] = 1;
			int a,b;
			cin>>a>>b;
			req.push_back(tiii(i,a,b));
		}
		else{
			int k;
			cin>>k;
			isask[i] = 2;
			req2.push_back(tiii(i,k,k));
		}
	}
	HLD::GO();
	for(auto &[w,s,e]:req){
		auto re = HLD::LCA(s,e);
		//cout<<w<<' '<<s<<' '<<e<<":"<<re.inc<<' '<<re.dec<<' '<<re.mx<<' '<<re.mn<<endl;
		if(!re.inc||re.mx>w)ans[w] = false;
		else ans[w] = true;
	}
	CD::GO();
	for(int i = 1;i<N+Q;i++){
		if(isask[i] == 1)cout<<(ans[i]?"yes\n":"no\n");
		else if(isask[i] == 2)cout<<ans[i]+1<<'\n';
	}
	return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 33476 KB Output is correct
2 Correct 105 ms 33868 KB Output is correct
3 Correct 55 ms 33800 KB Output is correct
4 Correct 82 ms 34012 KB Output is correct
5 Correct 67 ms 34560 KB Output is correct
6 Correct 58 ms 33836 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 33476 KB Output is correct
2 Correct 105 ms 33868 KB Output is correct
3 Correct 55 ms 33800 KB Output is correct
4 Correct 82 ms 34012 KB Output is correct
5 Correct 67 ms 34560 KB Output is correct
6 Correct 58 ms 33836 KB Output is correct
7 Correct 51 ms 32716 KB Output is correct
8 Correct 75 ms 33204 KB Output is correct
9 Correct 47 ms 33240 KB Output is correct
10 Correct 71 ms 33196 KB Output is correct
11 Correct 54 ms 33416 KB Output is correct
12 Correct 46 ms 33352 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 33280 KB Output is correct
2 Correct 114 ms 43384 KB Output is correct
3 Correct 122 ms 44404 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 33280 KB Output is correct
2 Correct 114 ms 43384 KB Output is correct
3 Correct 122 ms 44404 KB Output is correct
4 Correct 36 ms 32728 KB Output is correct
5 Correct 109 ms 42576 KB Output is correct
6 Correct 84 ms 42684 KB Output is correct
7 Correct 88 ms 42356 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 33476 KB Output is correct
2 Correct 286 ms 52108 KB Output is correct
3 Correct 289 ms 53764 KB Output is correct
4 Correct 209 ms 53572 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 33476 KB Output is correct
2 Correct 286 ms 52108 KB Output is correct
3 Correct 289 ms 53764 KB Output is correct
4 Correct 209 ms 53572 KB Output is correct
5 Correct 37 ms 32592 KB Output is correct
6 Correct 294 ms 52696 KB Output is correct
7 Correct 239 ms 52888 KB Output is correct
8 Correct 295 ms 53096 KB Output is correct
9 Correct 305 ms 53164 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 33480 KB Output is correct
2 Correct 320 ms 43340 KB Output is correct
3 Correct 258 ms 44888 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 33480 KB Output is correct
2 Correct 320 ms 43340 KB Output is correct
3 Correct 258 ms 44888 KB Output is correct
4 Correct 50 ms 32684 KB Output is correct
5 Correct 304 ms 44456 KB Output is correct
6 Correct 279 ms 45576 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 33476 KB Output is correct
2 Correct 298 ms 52100 KB Output is correct
3 Correct 278 ms 53612 KB Output is correct
4 Correct 236 ms 53616 KB Output is correct
5 Correct 46 ms 33476 KB Output is correct
6 Correct 324 ms 44952 KB Output is correct
7 Correct 261 ms 45096 KB Output is correct
8 Correct 411 ms 45768 KB Output is correct
9 Correct 279 ms 45756 KB Output is correct
10 Correct 267 ms 50744 KB Output is correct
11 Correct 332 ms 49888 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 33476 KB Output is correct
2 Correct 298 ms 52100 KB Output is correct
3 Correct 278 ms 53612 KB Output is correct
4 Correct 236 ms 53616 KB Output is correct
5 Correct 46 ms 33476 KB Output is correct
6 Correct 324 ms 44952 KB Output is correct
7 Correct 261 ms 45096 KB Output is correct
8 Correct 411 ms 45768 KB Output is correct
9 Correct 279 ms 45756 KB Output is correct
10 Correct 267 ms 50744 KB Output is correct
11 Correct 332 ms 49888 KB Output is correct
12 Correct 40 ms 32720 KB Output is correct
13 Correct 268 ms 52916 KB Output is correct
14 Correct 239 ms 52884 KB Output is correct
15 Correct 291 ms 53260 KB Output is correct
16 Correct 294 ms 53148 KB Output is correct
17 Correct 46 ms 32716 KB Output is correct
18 Correct 270 ms 44100 KB Output is correct
19 Correct 262 ms 45492 KB Output is correct
20 Correct 283 ms 44712 KB Output is correct
21 Correct 227 ms 44876 KB Output is correct
22 Correct 337 ms 47536 KB Output is correct
23 Correct 363 ms 48092 KB Output is correct
24 Correct 338 ms 47664 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 33408 KB Output is correct
2 Correct 106 ms 33972 KB Output is correct
3 Correct 56 ms 33992 KB Output is correct
4 Correct 86 ms 33996 KB Output is correct
5 Correct 62 ms 34180 KB Output is correct
6 Correct 57 ms 33964 KB Output is correct
7 Correct 44 ms 32932 KB Output is correct
8 Correct 105 ms 41332 KB Output is correct
9 Correct 127 ms 44212 KB Output is correct
10 Correct 38 ms 33476 KB Output is correct
11 Correct 265 ms 53596 KB Output is correct
12 Correct 266 ms 53760 KB Output is correct
13 Correct 221 ms 53616 KB Output is correct
14 Correct 48 ms 33512 KB Output is correct
15 Correct 318 ms 44832 KB Output is correct
16 Correct 248 ms 45060 KB Output is correct
17 Correct 357 ms 45776 KB Output is correct
18 Correct 237 ms 45740 KB Output is correct
19 Correct 273 ms 50688 KB Output is correct
20 Correct 330 ms 49904 KB Output is correct
21 Correct 139 ms 44720 KB Output is correct
22 Correct 138 ms 45056 KB Output is correct
23 Correct 183 ms 45064 KB Output is correct
24 Correct 182 ms 45200 KB Output is correct
25 Correct 275 ms 48616 KB Output is correct
26 Correct 202 ms 44244 KB Output is correct
27 Correct 226 ms 44264 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 33408 KB Output is correct
2 Correct 106 ms 33972 KB Output is correct
3 Correct 56 ms 33992 KB Output is correct
4 Correct 86 ms 33996 KB Output is correct
5 Correct 62 ms 34180 KB Output is correct
6 Correct 57 ms 33964 KB Output is correct
7 Correct 44 ms 32932 KB Output is correct
8 Correct 105 ms 41332 KB Output is correct
9 Correct 127 ms 44212 KB Output is correct
10 Correct 38 ms 33476 KB Output is correct
11 Correct 265 ms 53596 KB Output is correct
12 Correct 266 ms 53760 KB Output is correct
13 Correct 221 ms 53616 KB Output is correct
14 Correct 48 ms 33512 KB Output is correct
15 Correct 318 ms 44832 KB Output is correct
16 Correct 248 ms 45060 KB Output is correct
17 Correct 357 ms 45776 KB Output is correct
18 Correct 237 ms 45740 KB Output is correct
19 Correct 273 ms 50688 KB Output is correct
20 Correct 330 ms 49904 KB Output is correct
21 Correct 139 ms 44720 KB Output is correct
22 Correct 138 ms 45056 KB Output is correct
23 Correct 183 ms 45064 KB Output is correct
24 Correct 182 ms 45200 KB Output is correct
25 Correct 275 ms 48616 KB Output is correct
26 Correct 202 ms 44244 KB Output is correct
27 Correct 226 ms 44264 KB Output is correct
28 Correct 46 ms 32712 KB Output is correct
29 Correct 75 ms 33132 KB Output is correct
30 Correct 47 ms 33312 KB Output is correct
31 Correct 68 ms 33400 KB Output is correct
32 Correct 63 ms 33412 KB Output is correct
33 Correct 45 ms 33272 KB Output is correct
34 Correct 42 ms 32760 KB Output is correct
35 Correct 125 ms 42424 KB Output is correct
36 Correct 92 ms 42756 KB Output is correct
37 Correct 83 ms 42404 KB Output is correct
38 Correct 40 ms 32756 KB Output is correct
39 Correct 278 ms 52840 KB Output is correct
40 Correct 238 ms 52888 KB Output is correct
41 Correct 290 ms 53272 KB Output is correct
42 Correct 299 ms 53128 KB Output is correct
43 Correct 48 ms 32720 KB Output is correct
44 Correct 287 ms 44220 KB Output is correct
45 Correct 263 ms 45488 KB Output is correct
46 Correct 359 ms 44812 KB Output is correct
47 Correct 253 ms 44716 KB Output is correct
48 Correct 311 ms 47484 KB Output is correct
49 Correct 351 ms 48092 KB Output is correct
50 Correct 333 ms 47620 KB Output is correct
51 Correct 102 ms 43352 KB Output is correct
52 Correct 93 ms 43184 KB Output is correct
53 Correct 106 ms 42820 KB Output is correct
54 Correct 86 ms 43552 KB Output is correct
55 Correct 102 ms 43484 KB Output is correct
56 Correct 193 ms 43460 KB Output is correct
57 Correct 233 ms 46684 KB Output is correct
58 Correct 305 ms 44468 KB Output is correct
59 Correct 244 ms 43948 KB Output is correct