oj.uz

Submission #534504

# Submission time Handle Problem Language Result Execution time Memory
534504 2022-03-08T08:18:04 Z NhatMinh0208 Inside information (BOI21_servers) C++14
100 / 100
 1065 ms 75296 KB 
#ifndef CPL_TEMPLATE
#define CPL_TEMPLATE
/*
	Normie's Template v2.5
	Changes:
    Added warning against using pragmas on USACO.
*/
// Standard library in one include.
#include <bits/stdc++.h>
using namespace std;
 
// ordered_set library.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(el) tree<el,null_type,less<el>,rb_tree_tag,tree_order_statistics_node_update>
 
// AtCoder library. (Comment out these two lines if you're not submitting in AtCoder.) (Or if you want to use it in other judges, run expander.py first.)
//#include <atcoder/all>
//using namespace atcoder;
 
//Pragmas (Comment out these three lines if you're submitting in szkopul or USACO.)
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast,unroll-loops,tree-vectorize")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
 
//File I/O.
#define FILE_IN "cseq.inp"
#define FILE_OUT "cseq.out"
#define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout)
 
//Fast I/O.
#define fio ios::sync_with_stdio(0);cin.tie(0)
#define nfio cin.tie(0)
#define endl "\n"
 
//Order checking.
#define ord(a,b,c) ((a>=b)and(b>=c))
 
//min/max redefines, so i dont have to resolve annoying compile errors.
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))
 
// Fast min/max assigns to use with AVX.
// Requires g++ 9.2.0.
// template<typename T>
// __attribute__((always_inline)) void chkmin(T& a, const T& b) {
//     a=(a<b)?a:b;
// }
 
// template<typename T>
// __attribute__((always_inline)) void chkmax(T& a, const T& b) {
//     a=(a>b)?a:b;
// }
 
//Constants.
#define MOD (ll(998244353))
#define MAX 300001
#define mag 320
const long double PI=3.14159265358979;
 
//Pairs and 3-pairs.
#define p1 first
#define p2 second.first
#define p3 second.second
#define fi first
#define se second
#define pii(element_type) pair<element_type,element_type>
#define piii(element_type) pair<element_type,pii(element_type)>
 
//Quick power of 2.
#define pow2(x) (ll(1)<<x)
 
//Short for-loops.
#define ff(i,__,___) for(int i=__;i<=___;i++)
#define rr(i,__,___) for(int i=__;i>=___;i--)
 
//Typedefs.
#define bi BigInt
typedef long long ll;
typedef long double ld;
typedef short sh;
 
// Binpow and stuff
ll BOW(ll a, ll x, ll p)
{
	if (!x) return 1;
	ll res=BOW(a,x/2,p);
	res*=res;
	res%=p;
	if (x%2) res*=a;
	return res%p;
}
ll INV(ll a, ll p)
{
	return BOW(a,p-2,p);
}
//---------END-------//
#endif
vector<pii(int)> gt[120001];
vector<int> req[120001];

int n,m,i,j,k,t,t1,u,v,a,b;

int qt[240001];
int qx[240001];
int qy[240001];
int qres[240001];

int inc[120001][20];
int de[120001][20];
int jmp[120001][20];
pii(int) par[120001];
int dep[120001];
void init(int x, pii(int) p) {
	par[x]=p;
	dep[x]=dep[p.fi]+1;
	jmp[x][0]=p.fi;
	inc[x][0]=p.se;
	de[x][0]=p.se;
	int u;
	for (int i=1;i<20;i++) {
		u=jmp[x][i-1];
		jmp[x][i]=jmp[u][i-1];
		if (inc[x][i-1]==-1 || inc[u][i-1]==-1 || inc[x][i-1]>par[u].se) inc[x][i]=-1;
		else inc[x][i]=inc[u][i-1];
 
		if (de[x][i-1]==-1 || de[u][i-1]==-1 || de[x][i-1]<par[u].se) de[x][i]=-1;
		else de[x][i]=de[u][i-1];
		// cout<<x<<' '<<i<<' '<<jmp[x][i]<<' '<<de[x][i]<<' '<<inc[x][i]<<endl;
	}
	for (auto g : gt[x]) if (g.fi-p.fi) init(g.fi, {x,g.se});
}
 
int chk(int u, int v) {
	if (u==v) return 0;
	int cu=u,cv=v;
	int lu=-1e9,lv=1e9;
	for (int i=19;i>=0;i--) {
		if (dep[cu]-dep[cv]>=(1<<i)) {
			if (inc[cu][i]==-1 || lu>par[cu].se) return -1;
			lu=inc[cu][i];
			cu=jmp[cu][i];
		}
		if (dep[cv]-dep[cu]>=(1<<i)) {
			if (de[cv][i]==-1 || lv<par[cv].se) return -1;
			lv=de[cv][i];
			cv=jmp[cv][i];
		}
	}
	if (cu==cv) {
		if (cu==u) {
			return par[v].se;
		}
		else if (cu==v) {
			return lu;
		}
		else assert(0);
	}
	else {
		for (int i=19;i>=0;i--) if (jmp[cu][i]-jmp[cv][i]) {
			{
				if (inc[cu][i]==-1 || lu>par[cu].se) return -1;
				lu=inc[cu][i];
				cu=jmp[cu][i];
			}
			{
				if (de[cv][i]==-1 || lv<par[cv].se) return -1;
				lv=de[cv][i];
				cv=jmp[cv][i];
			}
		}
		if (lu<=par[cu].se && par[cu].se<=par[cv].se && par[cv].se<=lv) return par[v].se;
		else return -1;
	}
}

set<pii(int)> gts[120001];
int sz[120001];
ordered_set(pii(int)) sus;

void init2(int x, pii(int) p) {
	par[x]=p;
	if (x==p.fi) {
		inc[x][0]=1e9;
		de[x][0]=-1e9;
	}
	else {
		if ((inc[p.fi][0])and(inc[p.fi][0]>=p.se)) inc[x][0]=p.se; else inc[x][0]=0;
		if ((de[p.fi][0])and(de[p.fi][0]<=p.se)) de[x][0]=p.se; else de[x][0]=0;
	}
	
		// cout<<"init2 "<<x<<' '<<p.fi<<' '<<p.se<<' '<<inc[x][0]<<' '<<de[x][0]<<endl;
	for (auto g : gts[x]) if (p.fi-g.fi) init2(g.fi, {x,g.se});
}

void phase1(int x) {
	// cout<<"phase 1"<<x<<endl;
	if (inc[x][0]) {
		for (auto g : req[x]) {
			// cout<<"add "<<x<<' '<<g<<' '<<-qt[g]<<' '<<sus.order_of_key(pii(int)(-qt[g]+1,0))<<endl; 
			qres[g]+=sus.order_of_key(pii(int)(-qt[g]+1,0));
		}
	}
	for (auto g : gts[x]) if (g.fi-par[x].fi) phase1(g.fi);
}

void phase2(int x) {
	// cout<<"phase 2 "<<x<<' '<<de[x][0]<<endl;
	if (de[x][0]) {
		sus.insert({de[x][0],x});
	}
	for (auto g : gts[x]) if (g.fi-par[x].fi) phase2(g.fi);
}

void susz(int x, int p) {
	sz[x]=1;
	for (auto g : gts[x]) if (g.fi-p) {
		susz(g.fi,x);
		sz[x]+=sz[g.fi];
	}
}
void solve(int x) {
	// cout<<"solving for subtree "<<x<<endl;
	sus.clear();
	susz(x,x);
	if (sz[x]==1) {
		for (auto g : req[x]) qres[g]++;
		return;
	}

	int u=x,up=-1,a;

	// cout<<"finding centroid for "<<x<<endl;
	while(true) {
		// cout<<u<<endl;
		a=0;
		for (auto g : gts[u]) if (g.fi-up && sz[a]<sz[g.fi]) a=g.fi;
		if (sz[a]*2<=sz[x] && sz[u]*2>=sz[x]) break; else {
			up=u;
			u=a;
		}
	}

	// cout<<"found centroid "<<x<<' '<<u<<endl;

	init2(u,{u,0});
	vector<pii(int)> vec;
	for (auto g : gts[u]) vec.push_back(g);
	// for (auto g : vec) cout<<g.fi<<' '; cout<<endl;
	sort(vec.begin(), vec.end(), [](pii(int) a, pii(int) b){
		return (a.se>b.se);
	});
	for (auto g : vec) {
		sus.insert({g.se,u});
		phase1(g.fi);
		phase2(g.fi);
		sus.erase({g.se,u});
	}
	sus.insert({0,u});
	// for (auto g : sus) cout<<'('<<g.fi<<','<<g.se<<')'<<' ';
	// cout<<endl;
	
	
		for (auto g : req[u]) {
			// cout<<"add "<<u<<' '<<g<<' '<<-qt[g]<<' '<<sus.order_of_key(pii(int)(-qt[g]+1,0))<<endl; 
			qres[g]+=sus.order_of_key(pii(int)(-qt[g]+1,0));
		}

	for (auto g : vec) {
		gts[g.fi].erase({u,g.se});
		solve(g.fi);
	}
}

 
int main()
{
	fio;
	cin>>n>>m;
	char c;
	for (i=0;i<n+m-1;i++) {
		cin>>c;
		if (c=='S') {
			t++;
			qt[i]=t;
			cin>>qx[i]>>qy[i];
			// cout<<qx[i]<<' '<<qy[i]<<' '<<qt[i]<<endl;
			gt[qx[i]].push_back({qy[i],t});
			gt[qy[i]].push_back({qx[i],t});
			gts[qx[i]].insert({qy[i],t});
			gts[qy[i]].insert({qx[i],t});
		}
		else if (c=='Q') {
			qt[i]=-t;
			cin>>qx[i]>>qy[i];
		}
		else if (c=='C') {
			// return 0;
			qt[i]=-t;
			cin>>qx[i];
			req[qx[i]].push_back(i);
		}
	}
	init(1,{1,0});
	for (i=0;i<n+m-1;i++) if (qt[i]<=0 && qy[i]) {
		a = chk(qy[i],qx[i]);
		if (a==-1 || a>(-qt[i])) qres[i]=0; else qres[i]=1;
	}
	solve(1);
	for (i=0;i<n+m-1;i++) if (qt[i]<=0) {
		if (qy[i]==0) cout<<qres[i]<<endl;
		else if (qres[i]) cout<<"yes\n"; else cout<<"no\n";
	}
}
// a;

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 13892 KB Output is correct
2 Correct 44 ms 15336 KB Output is correct
3 Correct 48 ms 15464 KB Output is correct
4 Correct 41 ms 15492 KB Output is correct
5 Correct 55 ms 15616 KB Output is correct
6 Correct 48 ms 15776 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 13892 KB Output is correct
2 Correct 44 ms 15336 KB Output is correct
3 Correct 48 ms 15464 KB Output is correct
4 Correct 41 ms 15492 KB Output is correct
5 Correct 55 ms 15616 KB Output is correct
6 Correct 48 ms 15776 KB Output is correct
7 Correct 34 ms 13968 KB Output is correct
8 Correct 45 ms 15792 KB Output is correct
9 Correct 48 ms 15912 KB Output is correct
10 Correct 47 ms 15860 KB Output is correct
11 Correct 46 ms 16192 KB Output is correct
12 Correct 54 ms 16168 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 13816 KB Output is correct
2 Correct 539 ms 71064 KB Output is correct
3 Correct 546 ms 71104 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 13816 KB Output is correct
2 Correct 539 ms 71064 KB Output is correct
3 Correct 546 ms 71104 KB Output is correct
4 Correct 32 ms 13856 KB Output is correct
5 Correct 542 ms 69848 KB Output is correct
6 Correct 553 ms 70280 KB Output is correct
7 Correct 499 ms 70404 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 13900 KB Output is correct
2 Correct 755 ms 71532 KB Output is correct
3 Correct 644 ms 70872 KB Output is correct
4 Correct 440 ms 73996 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 13900 KB Output is correct
2 Correct 755 ms 71532 KB Output is correct
3 Correct 644 ms 70872 KB Output is correct
4 Correct 440 ms 73996 KB Output is correct
5 Correct 29 ms 13900 KB Output is correct
6 Correct 744 ms 71524 KB Output is correct
7 Correct 506 ms 74332 KB Output is correct
8 Correct 737 ms 72368 KB Output is correct
9 Correct 719 ms 72272 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 13764 KB Output is correct
2 Correct 408 ms 65112 KB Output is correct
3 Correct 523 ms 62100 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 13764 KB Output is correct
2 Correct 408 ms 65112 KB Output is correct
3 Correct 523 ms 62100 KB Output is correct
4 Correct 32 ms 13828 KB Output is correct
5 Correct 499 ms 66620 KB Output is correct
6 Correct 575 ms 62924 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 13884 KB Output is correct
2 Correct 707 ms 71500 KB Output is correct
3 Correct 664 ms 71460 KB Output is correct
4 Correct 491 ms 75124 KB Output is correct
5 Correct 31 ms 13772 KB Output is correct
6 Correct 431 ms 65204 KB Output is correct
7 Correct 478 ms 62072 KB Output is correct
8 Correct 629 ms 62544 KB Output is correct
9 Correct 596 ms 63488 KB Output is correct
10 Correct 803 ms 68220 KB Output is correct
11 Correct 816 ms 68292 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 13884 KB Output is correct
2 Correct 707 ms 71500 KB Output is correct
3 Correct 664 ms 71460 KB Output is correct
4 Correct 491 ms 75124 KB Output is correct
5 Correct 31 ms 13772 KB Output is correct
6 Correct 431 ms 65204 KB Output is correct
7 Correct 478 ms 62072 KB Output is correct
8 Correct 629 ms 62544 KB Output is correct
9 Correct 596 ms 63488 KB Output is correct
10 Correct 803 ms 68220 KB Output is correct
11 Correct 816 ms 68292 KB Output is correct
12 Correct 37 ms 13860 KB Output is correct
13 Correct 721 ms 71556 KB Output is correct
14 Correct 479 ms 74336 KB Output is correct
15 Correct 842 ms 72364 KB Output is correct
16 Correct 724 ms 72356 KB Output is correct
17 Correct 37 ms 13892 KB Output is correct
18 Correct 451 ms 66552 KB Output is correct
19 Correct 529 ms 63060 KB Output is correct
20 Correct 710 ms 63684 KB Output is correct
21 Correct 648 ms 63588 KB Output is correct
22 Correct 1018 ms 67772 KB Output is correct
23 Correct 1065 ms 68452 KB Output is correct
24 Correct 986 ms 67764 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 13892 KB Output is correct
2 Correct 47 ms 15400 KB Output is correct
3 Correct 47 ms 15520 KB Output is correct
4 Correct 50 ms 15708 KB Output is correct
5 Correct 42 ms 15684 KB Output is correct
6 Correct 53 ms 15796 KB Output is correct
7 Correct 35 ms 13916 KB Output is correct
8 Correct 535 ms 70644 KB Output is correct
9 Correct 510 ms 71092 KB Output is correct
10 Correct 30 ms 13772 KB Output is correct
11 Correct 677 ms 71528 KB Output is correct
12 Correct 680 ms 71588 KB Output is correct
13 Correct 446 ms 75296 KB Output is correct
14 Correct 33 ms 13808 KB Output is correct
15 Correct 452 ms 66428 KB Output is correct
16 Correct 515 ms 63348 KB Output is correct
17 Correct 618 ms 62404 KB Output is correct
18 Correct 606 ms 63496 KB Output is correct
19 Correct 854 ms 68972 KB Output is correct
20 Correct 890 ms 68464 KB Output is correct
21 Correct 593 ms 69456 KB Output is correct
22 Correct 531 ms 67040 KB Output is correct
23 Correct 614 ms 62352 KB Output is correct
24 Correct 637 ms 63668 KB Output is correct
25 Correct 911 ms 71416 KB Output is correct
26 Correct 525 ms 62532 KB Output is correct
27 Correct 508 ms 62356 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 13892 KB Output is correct
2 Correct 47 ms 15400 KB Output is correct
3 Correct 47 ms 15520 KB Output is correct
4 Correct 50 ms 15708 KB Output is correct
5 Correct 42 ms 15684 KB Output is correct
6 Correct 53 ms 15796 KB Output is correct
7 Correct 35 ms 13916 KB Output is correct
8 Correct 535 ms 70644 KB Output is correct
9 Correct 510 ms 71092 KB Output is correct
10 Correct 30 ms 13772 KB Output is correct
11 Correct 677 ms 71528 KB Output is correct
12 Correct 680 ms 71588 KB Output is correct
13 Correct 446 ms 75296 KB Output is correct
14 Correct 33 ms 13808 KB Output is correct
15 Correct 452 ms 66428 KB Output is correct
16 Correct 515 ms 63348 KB Output is correct
17 Correct 618 ms 62404 KB Output is correct
18 Correct 606 ms 63496 KB Output is correct
19 Correct 854 ms 68972 KB Output is correct
20 Correct 890 ms 68464 KB Output is correct
21 Correct 593 ms 69456 KB Output is correct
22 Correct 531 ms 67040 KB Output is correct
23 Correct 614 ms 62352 KB Output is correct
24 Correct 637 ms 63668 KB Output is correct
25 Correct 911 ms 71416 KB Output is correct
26 Correct 525 ms 62532 KB Output is correct
27 Correct 508 ms 62356 KB Output is correct
28 Correct 38 ms 13860 KB Output is correct
29 Correct 46 ms 15812 KB Output is correct
30 Correct 45 ms 15812 KB Output is correct
31 Correct 48 ms 15880 KB Output is correct
32 Correct 42 ms 16192 KB Output is correct
33 Correct 51 ms 16124 KB Output is correct
34 Correct 35 ms 13916 KB Output is correct
35 Correct 510 ms 69892 KB Output is correct
36 Correct 575 ms 70216 KB Output is correct
37 Correct 518 ms 70276 KB Output is correct
38 Correct 27 ms 13892 KB Output is correct
39 Correct 739 ms 71528 KB Output is correct
40 Correct 494 ms 74336 KB Output is correct
41 Correct 697 ms 72372 KB Output is correct
42 Correct 747 ms 72312 KB Output is correct
43 Correct 37 ms 13852 KB Output is correct
44 Correct 441 ms 66656 KB Output is correct
45 Correct 575 ms 62916 KB Output is correct
46 Correct 589 ms 63584 KB Output is correct
47 Correct 650 ms 63592 KB Output is correct
48 Correct 890 ms 67776 KB Output is correct
49 Correct 1006 ms 68376 KB Output is correct
50 Correct 945 ms 67764 KB Output is correct
51 Correct 591 ms 69716 KB Output is correct
52 Correct 506 ms 70196 KB Output is correct
53 Correct 506 ms 70196 KB Output is correct
54 Correct 468 ms 70260 KB Output is correct
55 Correct 496 ms 66880 KB Output is correct
56 Correct 603 ms 62744 KB Output is correct
57 Correct 806 ms 70244 KB Output is correct
58 Correct 579 ms 63120 KB Output is correct
59 Correct 472 ms 61672 KB Output is correct