oj.uz

Submission #963973

# Submission time Handle Problem Language Result Execution time Memory
963973 2024-04-16T06:12:08 Z pcc Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 83036 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 = 2e5+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 42 ms 23592 KB Output is correct
2 Correct 95 ms 24300 KB Output is correct
3 Correct 61 ms 24576 KB Output is correct
4 Correct 79 ms 24508 KB Output is correct
5 Correct 58 ms 24832 KB Output is correct
6 Correct 48 ms 24296 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 23592 KB Output is correct
2 Correct 95 ms 24300 KB Output is correct
3 Correct 61 ms 24576 KB Output is correct
4 Correct 79 ms 24508 KB Output is correct
5 Correct 58 ms 24832 KB Output is correct
6 Correct 48 ms 24296 KB Output is correct
7 Correct 42 ms 22992 KB Output is correct
8 Correct 69 ms 23412 KB Output is correct
9 Correct 42 ms 23652 KB Output is correct
10 Correct 61 ms 23476 KB Output is correct
11 Correct 50 ms 23684 KB Output is correct
12 Correct 47 ms 23368 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 23904 KB Output is correct
2 Runtime error 108 ms 64588 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 23904 KB Output is correct
2 Runtime error 108 ms 64588 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 23760 KB Output is correct
2 Runtime error 129 ms 82948 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 23760 KB Output is correct
2 Runtime error 129 ms 82948 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 23764 KB Output is correct
2 Execution timed out 3531 ms 34004 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 23764 KB Output is correct
2 Execution timed out 3531 ms 34004 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 23744 KB Output is correct
2 Runtime error 135 ms 83036 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 23744 KB Output is correct
2 Runtime error 135 ms 83036 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 23680 KB Output is correct
2 Correct 96 ms 24464 KB Output is correct
3 Correct 51 ms 24512 KB Output is correct
4 Correct 92 ms 24588 KB Output is correct
5 Correct 73 ms 24832 KB Output is correct
6 Correct 49 ms 24504 KB Output is correct
7 Correct 33 ms 23760 KB Output is correct
8 Runtime error 107 ms 64312 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 23680 KB Output is correct
2 Correct 96 ms 24464 KB Output is correct
3 Correct 51 ms 24512 KB Output is correct
4 Correct 92 ms 24588 KB Output is correct
5 Correct 73 ms 24832 KB Output is correct
6 Correct 49 ms 24504 KB Output is correct
7 Correct 33 ms 23760 KB Output is correct
8 Runtime error 107 ms 64312 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -