oj.uz

Submission #581967

# Submission time Handle Problem Language Result Execution time Memory
581967 2022-06-23T08:45:14 Z WongChun1234 Inside information (BOI21_servers) C++14
20 / 100
 3500 ms 370704 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];
char ty[Q];
bool del[N];
map<pair<int,int>,int> t;
map<int,int> tonde[N],frmnde[N],incen[N];
vector<int> adj[N];
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 (t[{nde,i}]>mxdist){
			comp(i,nde,smallrt,bigrt,INT_MIN,t[{nde,i}]);
		}else if (t[{nde,i}]<mindist){
			comp(i,nde,smallrt,bigrt,t[{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,t[{cen,i}],t[{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 (t[{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 (t[{incen[v][rt],rt}]>t[{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]);
			t[{u[i],v[i]}]=i;
			t[{v[i],u[i]}]=i;
		}else if (ty[i]=='Q'){
			cin>>v[i];
		}else{
			//???
		}
	}
	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 84 ms 21552 KB Output is correct
2 Correct 775 ms 48196 KB Output is correct
3 Correct 152 ms 26408 KB Output is correct
4 Correct 970 ms 58864 KB Output is correct
5 Correct 925 ms 62008 KB Output is correct
6 Correct 116 ms 25568 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 84 ms 21552 KB Output is correct
2 Correct 775 ms 48196 KB Output is correct
3 Correct 152 ms 26408 KB Output is correct
4 Correct 970 ms 58864 KB Output is correct
5 Correct 925 ms 62008 KB Output is correct
6 Correct 116 ms 25568 KB Output is correct
7 Incorrect 88 ms 21664 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 63 ms 21524 KB Output is correct
2 Correct 781 ms 62124 KB Output is correct
3 Correct 742 ms 62148 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 21524 KB Output is correct
2 Correct 781 ms 62124 KB Output is correct
3 Correct 742 ms 62148 KB Output is correct
4 Incorrect 67 ms 21520 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 84 ms 21544 KB Output is correct
2 Correct 1902 ms 311944 KB Output is correct
3 Correct 1753 ms 311788 KB Output is correct
4 Correct 2058 ms 370464 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 21544 KB Output is correct
2 Correct 1902 ms 311944 KB Output is correct
3 Correct 1753 ms 311788 KB Output is correct
4 Correct 2058 ms 370464 KB Output is correct
5 Incorrect 81 ms 21560 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 80 ms 21500 KB Output is correct
2 Correct 1674 ms 265732 KB Output is correct
3 Correct 1766 ms 235440 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 21500 KB Output is correct
2 Correct 1674 ms 265732 KB Output is correct
3 Correct 1766 ms 235440 KB Output is correct
4 Incorrect 77 ms 21528 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 90 ms 21604 KB Output is correct
2 Correct 1787 ms 311788 KB Output is correct
3 Correct 1786 ms 311728 KB Output is correct
4 Correct 1968 ms 370704 KB Output is correct
5 Correct 80 ms 21512 KB Output is correct
6 Correct 1610 ms 265700 KB Output is correct
7 Correct 1744 ms 235512 KB Output is correct
8 Correct 2537 ms 269496 KB Output is correct
9 Correct 2326 ms 225376 KB Output is correct
10 Correct 3366 ms 305316 KB Output is correct
11 Execution timed out 3537 ms 341184 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 90 ms 21604 KB Output is correct
2 Correct 1787 ms 311788 KB Output is correct
3 Correct 1786 ms 311728 KB Output is correct
4 Correct 1968 ms 370704 KB Output is correct
5 Correct 80 ms 21512 KB Output is correct
6 Correct 1610 ms 265700 KB Output is correct
7 Correct 1744 ms 235512 KB Output is correct
8 Correct 2537 ms 269496 KB Output is correct
9 Correct 2326 ms 225376 KB Output is correct
10 Correct 3366 ms 305316 KB Output is correct
11 Execution timed out 3537 ms 341184 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 82 ms 21580 KB Output is correct
2 Correct 689 ms 48088 KB Output is correct
3 Correct 159 ms 26368 KB Output is correct
4 Correct 1059 ms 58804 KB Output is correct
5 Correct 907 ms 62140 KB Output is correct
6 Correct 125 ms 25484 KB Output is correct
7 Correct 63 ms 21560 KB Output is correct
8 Correct 773 ms 62116 KB Output is correct
9 Correct 795 ms 62120 KB Output is correct
10 Correct 87 ms 21508 KB Output is correct
11 Correct 1798 ms 311824 KB Output is correct
12 Correct 1812 ms 311788 KB Output is correct
13 Correct 2033 ms 370636 KB Output is correct
14 Correct 80 ms 21568 KB Output is correct
15 Correct 1589 ms 265856 KB Output is correct
16 Correct 1779 ms 235360 KB Output is correct
17 Correct 2557 ms 269668 KB Output is correct
18 Correct 2294 ms 225520 KB Output is correct
19 Correct 3282 ms 305224 KB Output is correct
20 Execution timed out 3580 ms 341084 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 82 ms 21580 KB Output is correct
2 Correct 689 ms 48088 KB Output is correct
3 Correct 159 ms 26368 KB Output is correct
4 Correct 1059 ms 58804 KB Output is correct
5 Correct 907 ms 62140 KB Output is correct
6 Correct 125 ms 25484 KB Output is correct
7 Correct 63 ms 21560 KB Output is correct
8 Correct 773 ms 62116 KB Output is correct
9 Correct 795 ms 62120 KB Output is correct
10 Correct 87 ms 21508 KB Output is correct
11 Correct 1798 ms 311824 KB Output is correct
12 Correct 1812 ms 311788 KB Output is correct
13 Correct 2033 ms 370636 KB Output is correct
14 Correct 80 ms 21568 KB Output is correct
15 Correct 1589 ms 265856 KB Output is correct
16 Correct 1779 ms 235360 KB Output is correct
17 Correct 2557 ms 269668 KB Output is correct
18 Correct 2294 ms 225520 KB Output is correct
19 Correct 3282 ms 305224 KB Output is correct
20 Execution timed out 3580 ms 341084 KB Time limit exceeded
21 Halted 0 ms 0 KB -