oj.uz

Submission #581991

# Submission time Handle Problem Language Result Execution time Memory
581991 2022-06-23T09:18:07 Z WongChun1234 Inside information (BOI21_servers) C++14
50 / 100
 3261 ms 353620 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=120050;
const int Q=240050;
const bool DEBUG=0;
int n,k,sz[N],u[Q],v[Q],t[N],preord[N],postord[N],pt;
char ty[Q];
bool del[N];
map<int,int> tonde[N],frmnde[N],incen[N];
vector<int> adj[N];
void mainprec(int nde,int par){
	preord[nde]=++pt;
	for (int i:adj[nde]) if (i!=par) mainprec(i,nde);
	postord[nde]=pt;
}
bool isa(int a,int b){
	return (preord[a]<=preord[b]&&postord[a]>=postord[b]);
}
int qedge(int a,int b){
	return (isa(a,b)?t[b]:t[a]);
}
void prec(int nde,int par){
	sz[nde]=1;
	for (int i:adj[nde]){
		if (del[i]) continue;
		if (i==par) continue;
		prec(i,nde);
		sz[nde]+=sz[i];
	}
}
int findcen(int nde,int par,int mx){
	for (int i:adj[nde]){
		if (del[i]) continue;
		if (i==par) continue;
		if (sz[i]>mx/2) return findcen(i,nde,mx);
	}
	return nde;
}
void comp(int nde,int par,int smallrt,int bigrt,int mindist,int mxdist){
	if (DEBUG) cerr<<nde<<":"<<par<<" "<<smallrt<<","<<bigrt<<"::"<<mindist<<","<<mxdist<<"\n";
	incen[nde][bigrt]=smallrt;
	tonde[bigrt][nde]=mxdist;
	frmnde[bigrt][nde]=mindist;
	for (int i:adj[nde]){
		if (del[i]) continue;
		if (i==par) continue;
		if (qedge(nde,i)>mxdist){
			comp(i,nde,smallrt,bigrt,INT_MIN,qedge(nde,i));
		}else if (qedge(nde,i)<mindist){
			comp(i,nde,smallrt,bigrt,qedge(nde,i),INT_MAX);
		}else{
			comp(i,nde,smallrt,bigrt,INT_MIN,INT_MAX);
		}
	}
}
void dc(int nde){
	prec(nde,nde);
	int cen=findcen(nde,nde,sz[nde]);
	if (DEBUG) cerr<<nde<<":"<<cen<<"uwuuwu\n";
	del[cen]=1;
	for (int i:adj[cen]){
		if (del[i]) continue;
		comp(i,cen,i,cen,qedge(cen,i),qedge(cen,i));
	}
	for (int i:adj[cen]){
		if (del[i]) continue;
		dc(i);
	}
}
bool check(int rt,int v,int u,int id){
	// v->u
	if (u==rt){
		if (frmnde[rt][v]==INT_MIN) return 0;
		return (qedge(rt,incen[v][rt])<=id);
	}else if (v==rt){
		if (tonde[rt][u]==INT_MAX) return 0;
		return (tonde[rt][u]<=id);
	}else{
		if (incen[u][rt]==incen[v][rt]) return 0;
		if (qedge(incen[v][rt],rt)>qedge(incen[u][rt],rt)) return 0;
		if (frmnde[rt][v]==INT_MIN) return 0;
		if (tonde[rt][u]>id) return 0;
		return 1;
	}
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>k;
	for (int i=1;i<n+k;i++){
		cin>>ty[i]>>u[i];
		if (ty[i]=='S'){
			cin>>v[i];
			adj[u[i]].push_back(v[i]);
			adj[v[i]].push_back(u[i]);
		}else if (ty[i]=='Q'){
			cin>>v[i];
		}else{
			//???
		}
	}
	mainprec(1,1);
	for (int i=1;i<n+k;i++){
		if (ty[i]!='S') continue;
		if (isa(u[i],v[i])) t[v[i]]=i;
		else t[u[i]]=i;
	}
	dc(1);
	for (int i=1;i<n+k;i++){
		if (ty[i]=='Q'){
			//check if v->u exists
			if (u[i]==v[i]){
				cout<<"yes\n";
				goto skip;
			}
			if (DEBUG) cerr<<v[i]<<",,"<<u[i]<<"\n";
			for (auto j:incen[v[i]]){
				if (!j.second) continue;
				if (DEBUG) cerr<<j.first<<"::"<<j.second<<"a\n";
				if ((!!incen[u[i]][j.first])||j.first==u[i]){
					if (DEBUG) cerr<<v[i]<<"->"<<incen[v[i]][j.first]<<"--"<<j.first<<"--"<<incen[u[i]][j.first]<<"->"<<u[i]<<"\n";
					if (check(j.first,v[i],u[i],i)){
						cout<<"yes\n";
						goto skip;
					}
				}
			}
			if (incen[u[i]][v[i]]){
				if (check(v[i],v[i],u[i],i)){
					cout<<"yes\n";
					goto skip;
				}
			}
			cout<<"no\n";
			skip:;
		}else if (ty[i]=='C'){
			cout<<"42\n";
		}
	}
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 94 ms 21688 KB Output is correct
2 Correct 849 ms 47080 KB Output is correct
3 Correct 218 ms 26104 KB Output is correct
4 Correct 1148 ms 58512 KB Output is correct
5 Correct 1066 ms 60900 KB Output is correct
6 Correct 154 ms 25192 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 94 ms 21688 KB Output is correct
2 Correct 849 ms 47080 KB Output is correct
3 Correct 218 ms 26104 KB Output is correct
4 Correct 1148 ms 58512 KB Output is correct
5 Correct 1066 ms 60900 KB Output is correct
6 Correct 154 ms 25192 KB Output is correct
7 Incorrect 100 ms 21640 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 73 ms 21760 KB Output is correct
2 Correct 434 ms 48808 KB Output is correct
3 Correct 405 ms 48704 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 73 ms 21760 KB Output is correct
2 Correct 434 ms 48808 KB Output is correct
3 Correct 405 ms 48704 KB Output is correct
4 Incorrect 81 ms 21684 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 21688 KB Output is correct
2 Correct 1535 ms 295456 KB Output is correct
3 Correct 1507 ms 295472 KB Output is correct
4 Correct 1870 ms 353552 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 21688 KB Output is correct
2 Correct 1535 ms 295456 KB Output is correct
3 Correct 1507 ms 295472 KB Output is correct
4 Correct 1870 ms 353552 KB Output is correct
5 Incorrect 87 ms 21716 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 21648 KB Output is correct
2 Correct 1821 ms 305748 KB Output is correct
3 Correct 1535 ms 267344 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 21648 KB Output is correct
2 Correct 1821 ms 305748 KB Output is correct
3 Correct 1535 ms 267344 KB Output is correct
4 Incorrect 93 ms 21684 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 106 ms 21724 KB Output is correct
2 Correct 1370 ms 295496 KB Output is correct
3 Correct 1349 ms 295400 KB Output is correct
4 Correct 1676 ms 353620 KB Output is correct
5 Correct 106 ms 21636 KB Output is correct
6 Correct 1582 ms 305828 KB Output is correct
7 Correct 1579 ms 267376 KB Output is correct
8 Correct 2145 ms 255944 KB Output is correct
9 Correct 1852 ms 211592 KB Output is correct
10 Correct 2672 ms 290932 KB Output is correct
11 Correct 3261 ms 326608 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 106 ms 21724 KB Output is correct
2 Correct 1370 ms 295496 KB Output is correct
3 Correct 1349 ms 295400 KB Output is correct
4 Correct 1676 ms 353620 KB Output is correct
5 Correct 106 ms 21636 KB Output is correct
6 Correct 1582 ms 305828 KB Output is correct
7 Correct 1579 ms 267376 KB Output is correct
8 Correct 2145 ms 255944 KB Output is correct
9 Correct 1852 ms 211592 KB Output is correct
10 Correct 2672 ms 290932 KB Output is correct
11 Correct 3261 ms 326608 KB Output is correct
12 Incorrect 108 ms 22444 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 108 ms 21648 KB Output is correct
2 Correct 898 ms 47080 KB Output is correct
3 Correct 177 ms 26032 KB Output is correct
4 Correct 1249 ms 58440 KB Output is correct
5 Correct 1130 ms 60836 KB Output is correct
6 Correct 144 ms 25244 KB Output is correct
7 Correct 98 ms 21716 KB Output is correct
8 Correct 458 ms 48652 KB Output is correct
9 Correct 407 ms 48576 KB Output is correct
10 Correct 101 ms 21712 KB Output is correct
11 Correct 1645 ms 295452 KB Output is correct
12 Correct 1660 ms 295468 KB Output is correct
13 Correct 1829 ms 353552 KB Output is correct
14 Correct 94 ms 21656 KB Output is correct
15 Correct 1791 ms 305828 KB Output is correct
16 Correct 1637 ms 267344 KB Output is correct
17 Correct 2295 ms 255888 KB Output is correct
18 Correct 1832 ms 211532 KB Output is correct
19 Correct 2594 ms 290912 KB Output is correct
20 Correct 2720 ms 326512 KB Output is correct
21 Correct 600 ms 61512 KB Output is correct
22 Correct 558 ms 64228 KB Output is correct
23 Correct 1278 ms 142588 KB Output is correct
24 Correct 1377 ms 142004 KB Output is correct
25 Correct 1643 ms 184492 KB Output is correct
26 Correct 1282 ms 171772 KB Output is correct
27 Correct 1253 ms 170084 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 108 ms 21648 KB Output is correct
2 Correct 898 ms 47080 KB Output is correct
3 Correct 177 ms 26032 KB Output is correct
4 Correct 1249 ms 58440 KB Output is correct
5 Correct 1130 ms 60836 KB Output is correct
6 Correct 144 ms 25244 KB Output is correct
7 Correct 98 ms 21716 KB Output is correct
8 Correct 458 ms 48652 KB Output is correct
9 Correct 407 ms 48576 KB Output is correct
10 Correct 101 ms 21712 KB Output is correct
11 Correct 1645 ms 295452 KB Output is correct
12 Correct 1660 ms 295468 KB Output is correct
13 Correct 1829 ms 353552 KB Output is correct
14 Correct 94 ms 21656 KB Output is correct
15 Correct 1791 ms 305828 KB Output is correct
16 Correct 1637 ms 267344 KB Output is correct
17 Correct 2295 ms 255888 KB Output is correct
18 Correct 1832 ms 211532 KB Output is correct
19 Correct 2594 ms 290912 KB Output is correct
20 Correct 2720 ms 326512 KB Output is correct
21 Correct 600 ms 61512 KB Output is correct
22 Correct 558 ms 64228 KB Output is correct
23 Correct 1278 ms 142588 KB Output is correct
24 Correct 1377 ms 142004 KB Output is correct
25 Correct 1643 ms 184492 KB Output is correct
26 Correct 1282 ms 171772 KB Output is correct
27 Correct 1253 ms 170084 KB Output is correct
28 Incorrect 97 ms 22440 KB Extra information in the output file
29 Halted 0 ms 0 KB -