oj.uz

Submission #963927

# Submission time Handle Problem Language Result Execution time Memory
963927 2024-04-16T03:38:23 Z pcc Inside information (BOI21_servers) C++17
53 / 100
 212 ms 37456 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;

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);
	}
}

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'){
			int a,b;
			cin>>a>>b;
			req.push_back(tiii(i,a,b));
		}
		else{
			exit(0);
		}
	}
	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)cout<<"no\n";
		else cout<<"yes\n";
	}
	return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 19660 KB Output is correct
2 Correct 96 ms 21232 KB Output is correct
3 Correct 47 ms 21432 KB Output is correct
4 Correct 81 ms 21456 KB Output is correct
5 Correct 57 ms 21520 KB Output is correct
6 Correct 42 ms 21224 KB Output is correct

Subtask #2
0.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 19660 KB Output is correct
2 Correct 96 ms 21232 KB Output is correct
3 Correct 47 ms 21432 KB Output is correct
4 Correct 81 ms 21456 KB Output is correct
5 Correct 57 ms 21520 KB Output is correct
6 Correct 42 ms 21224 KB Output is correct
7 Partially correct 4 ms 15964 KB Output is incorrect
8 Partially correct 4 ms 15708 KB Output is incorrect
9 Partially correct 5 ms 15960 KB Output is incorrect
10 Partially correct 4 ms 15708 KB Output is incorrect
11 Partially correct 4 ms 15708 KB Output is incorrect
12 Partially correct 4 ms 15708 KB Output is incorrect

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 19760 KB Output is correct
2 Correct 105 ms 27996 KB Output is correct
3 Correct 81 ms 28020 KB Output is correct

Subtask #4
0.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 19760 KB Output is correct
2 Correct 105 ms 27996 KB Output is correct
3 Correct 81 ms 28020 KB Output is correct
4 Partially correct 4 ms 15964 KB Output is incorrect
5 Partially correct 4 ms 15708 KB Output is incorrect
6 Partially correct 4 ms 15704 KB Output is incorrect
7 Partially correct 5 ms 15708 KB Output is incorrect

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 19636 KB Output is correct
2 Correct 101 ms 37300 KB Output is correct
3 Correct 100 ms 37456 KB Output is correct
4 Correct 106 ms 37312 KB Output is correct

Subtask #6
0.5 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 19636 KB Output is correct
2 Correct 101 ms 37300 KB Output is correct
3 Correct 100 ms 37456 KB Output is correct
4 Correct 106 ms 37312 KB Output is correct
5 Partially correct 4 ms 15964 KB Output is incorrect
6 Partially correct 5 ms 15708 KB Output is incorrect
7 Partially correct 4 ms 15708 KB Output is incorrect
8 Partially correct 4 ms 15708 KB Output is incorrect
9 Partially correct 4 ms 15716 KB Output is incorrect

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 19852 KB Output is correct
2 Correct 203 ms 28700 KB Output is correct
3 Correct 84 ms 29188 KB Output is correct

Subtask #8
0.5 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 19852 KB Output is correct
2 Correct 203 ms 28700 KB Output is correct
3 Correct 84 ms 29188 KB Output is correct
4 Partially correct 7 ms 16112 KB Output is incorrect
5 Partially correct 4 ms 15708 KB Output is incorrect
6 Partially correct 19 ms 19548 KB Output is incorrect

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 19844 KB Output is correct
2 Correct 114 ms 37420 KB Output is correct
3 Correct 84 ms 37292 KB Output is correct
4 Correct 101 ms 37264 KB Output is correct
5 Correct 37 ms 20680 KB Output is correct
6 Correct 205 ms 28604 KB Output is correct
7 Correct 103 ms 29108 KB Output is correct
8 Correct 212 ms 29396 KB Output is correct
9 Correct 104 ms 29364 KB Output is correct
10 Correct 99 ms 34352 KB Output is correct
11 Correct 158 ms 33412 KB Output is correct

Subtask #10
0.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 19844 KB Output is correct
2 Correct 114 ms 37420 KB Output is correct
3 Correct 84 ms 37292 KB Output is correct
4 Correct 101 ms 37264 KB Output is correct
5 Correct 37 ms 20680 KB Output is correct
6 Correct 205 ms 28604 KB Output is correct
7 Correct 103 ms 29108 KB Output is correct
8 Correct 212 ms 29396 KB Output is correct
9 Correct 104 ms 29364 KB Output is correct
10 Correct 99 ms 34352 KB Output is correct
11 Correct 158 ms 33412 KB Output is correct
12 Partially correct 4 ms 15968 KB Output is incorrect
13 Partially correct 4 ms 15708 KB Output is incorrect
14 Partially correct 4 ms 15708 KB Output is incorrect
15 Partially correct 4 ms 15708 KB Output is incorrect
16 Partially correct 4 ms 15708 KB Output is incorrect
17 Partially correct 4 ms 15964 KB Output is incorrect
18 Partially correct 4 ms 15936 KB Output is incorrect
19 Partially correct 24 ms 19548 KB Output is incorrect
20 Partially correct 4 ms 15704 KB Output is incorrect
21 Partially correct 4 ms 15708 KB Output is incorrect
22 Partially correct 4 ms 15708 KB Output is incorrect
23 Partially correct 25 ms 19840 KB Output is incorrect
24 Partially correct 26 ms 20904 KB Output is incorrect

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 19716 KB Output is correct
2 Correct 88 ms 21304 KB Output is correct
3 Correct 43 ms 21228 KB Output is correct
4 Correct 88 ms 21220 KB Output is correct
5 Correct 52 ms 21516 KB Output is correct
6 Correct 41 ms 21224 KB Output is correct
7 Correct 30 ms 20732 KB Output is correct
8 Correct 88 ms 27796 KB Output is correct
9 Correct 91 ms 27992 KB Output is correct
10 Correct 28 ms 20684 KB Output is correct
11 Correct 92 ms 37376 KB Output is correct
12 Correct 88 ms 37380 KB Output is correct
13 Correct 99 ms 37128 KB Output is correct
14 Correct 37 ms 20720 KB Output is correct
15 Correct 210 ms 28640 KB Output is correct
16 Correct 91 ms 29008 KB Output is correct
17 Correct 208 ms 29396 KB Output is correct
18 Correct 126 ms 29628 KB Output is correct
19 Correct 95 ms 34360 KB Output is correct
20 Correct 147 ms 33472 KB Output is correct
21 Correct 88 ms 28528 KB Output is correct
22 Correct 95 ms 28672 KB Output is correct
23 Correct 104 ms 28876 KB Output is correct
24 Correct 111 ms 28760 KB Output is correct
25 Correct 90 ms 31036 KB Output is correct
26 Correct 92 ms 28736 KB Output is correct
27 Correct 86 ms 29000 KB Output is correct

Subtask #12
0.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 19716 KB Output is correct
2 Correct 88 ms 21304 KB Output is correct
3 Correct 43 ms 21228 KB Output is correct
4 Correct 88 ms 21220 KB Output is correct
5 Correct 52 ms 21516 KB Output is correct
6 Correct 41 ms 21224 KB Output is correct
7 Correct 30 ms 20732 KB Output is correct
8 Correct 88 ms 27796 KB Output is correct
9 Correct 91 ms 27992 KB Output is correct
10 Correct 28 ms 20684 KB Output is correct
11 Correct 92 ms 37376 KB Output is correct
12 Correct 88 ms 37380 KB Output is correct
13 Correct 99 ms 37128 KB Output is correct
14 Correct 37 ms 20720 KB Output is correct
15 Correct 210 ms 28640 KB Output is correct
16 Correct 91 ms 29008 KB Output is correct
17 Correct 208 ms 29396 KB Output is correct
18 Correct 126 ms 29628 KB Output is correct
19 Correct 95 ms 34360 KB Output is correct
20 Correct 147 ms 33472 KB Output is correct
21 Correct 88 ms 28528 KB Output is correct
22 Correct 95 ms 28672 KB Output is correct
23 Correct 104 ms 28876 KB Output is correct
24 Correct 111 ms 28760 KB Output is correct
25 Correct 90 ms 31036 KB Output is correct
26 Correct 92 ms 28736 KB Output is correct
27 Correct 86 ms 29000 KB Output is correct
28 Partially correct 4 ms 15964 KB Output is incorrect
29 Partially correct 4 ms 15708 KB Output is incorrect
30 Partially correct 4 ms 15936 KB Output is incorrect
31 Partially correct 5 ms 15964 KB Output is incorrect
32 Partially correct 4 ms 15708 KB Output is incorrect
33 Partially correct 4 ms 15708 KB Output is incorrect
34 Partially correct 4 ms 15960 KB Output is incorrect
35 Partially correct 4 ms 15708 KB Output is incorrect
36 Partially correct 5 ms 15708 KB Output is incorrect
37 Partially correct 5 ms 15708 KB Output is incorrect
38 Partially correct 4 ms 16220 KB Output is incorrect
39 Partially correct 4 ms 15708 KB Output is incorrect
40 Partially correct 4 ms 15888 KB Output is incorrect
41 Partially correct 4 ms 15708 KB Output is incorrect
42 Partially correct 4 ms 15704 KB Output is incorrect
43 Partially correct 5 ms 15960 KB Output is incorrect
44 Partially correct 4 ms 15704 KB Output is incorrect
45 Partially correct 23 ms 19576 KB Output is incorrect
46 Partially correct 4 ms 15708 KB Output is incorrect
47 Partially correct 4 ms 15708 KB Output is incorrect
48 Partially correct 4 ms 15708 KB Output is incorrect
49 Partially correct 27 ms 19804 KB Output is incorrect
50 Partially correct 25 ms 20828 KB Output is incorrect
51 Partially correct 5 ms 15708 KB Output is incorrect
52 Partially correct 4 ms 15708 KB Output is incorrect
53 Partially correct 4 ms 15704 KB Output is incorrect
54 Partially correct 4 ms 15708 KB Output is incorrect
55 Partially correct 4 ms 15708 KB Output is incorrect
56 Partially correct 5 ms 15708 KB Output is incorrect
57 Partially correct 5 ms 16116 KB Output is incorrect
58 Partially correct 27 ms 20568 KB Output is incorrect
59 Partially correct 43 ms 22100 KB Output is incorrect