oj.uz

Submission #557184

# Submission time Handle Problem Language Result Execution time Memory
557184 2022-05-04T20:36:26 Z MilosMilutinovic Inside information (BOI21_servers) C++14
50 / 100
 248 ms 30428 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
const int N=120050;
const int M=2*N;
const int L=20;
int n,q,op[M],x[M],y[M],par[N][L],dep[N],w[N],up[N],dw[N];
vector<pii> E[N];
void DFS1(int u,int p){
	if(w[u]>w[p])dw[u]=dw[p],up[u]=p;
	else up[u]=up[p],dw[u]=p;
	dep[u]=dep[p]+1;
	par[u][0]=p;
	for(int i=1;i<L;i++)par[u][i]=par[par[u][i-1]][i-1];
	for(auto e:E[u])if(e.first!=p){
		w[e.first]=e.second;
		DFS1(e.first,u);
	}
}
int LCA(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	for(int i=L-1;~i;i--)if(dep[par[u][i]]>=dep[v])u=par[u][i];
	for(int i=L-1;~i;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
	return u==v?u:par[u][0];
}
int Lift(int u,int k){for(int i=L-1;i>=0;i--)if(k>>i&1)u=par[u][i];return u;}
bool conn(int u,int v,int t){
	bool ok=true;
	int lca=LCA(u,v);
	if(u!=lca&&v!=lca){
		int pu=Lift(u,dep[u]-dep[lca]-1);
		int pv=Lift(v,dep[v]-dep[lca]-1);
		if(w[pu]<w[pv])ok=false;
	}
	if(u!=lca&&dep[lca]<dep[dw[u]])ok=false;
	if(v!=lca&&dep[lca]<dep[up[v]])ok=false;
	if(u!=lca&&w[u]>t)ok=false;
	if(v!=lca&&w[Lift(v,dep[v]-dep[lca]-1)]>t)ok=false;
	return ok;
}
int main(){
	scanf("%i%i",&n,&q);
	q+=n-1;
	for(int i=1;i<=q;i++){
		char ch;
		scanf("\n%c %i",&ch,&x[i]);
		op[i]=(ch=='S'?1:(ch=='Q'?2:3));
		if(op[i]!=3)scanf("%i",&y[i]);
		if(op[i]==1){
			E[x[i]].pb(mp(y[i],i));
			E[y[i]].pb(mp(x[i],i));
		}
	}
	w[1]=1000000;
	up[1]=dw[1]=1;
	DFS1(1,1);
	for(int i=1;i<=q;i++){
		if(op[i]==1)continue;
		if(op[i]==2){
			puts(conn(x[i],y[i],i)?"yes":"no");
			continue;
		}
	}
	return 0;
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  scanf("%i%i",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
servers.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("\n%c %i",&ch,&x[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~
servers.cpp:50:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   if(op[i]!=3)scanf("%i",&y[i]);
      |               ~~~~~^~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 69 ms 5820 KB Output is correct
2 Correct 77 ms 6784 KB Output is correct
3 Correct 72 ms 6940 KB Output is correct
4 Correct 84 ms 6860 KB Output is correct
5 Correct 71 ms 7012 KB Output is correct
6 Correct 76 ms 6900 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 69 ms 5820 KB Output is correct
2 Correct 77 ms 6784 KB Output is correct
3 Correct 72 ms 6940 KB Output is correct
4 Correct 84 ms 6860 KB Output is correct
5 Correct 71 ms 7012 KB Output is correct
6 Correct 76 ms 6900 KB Output is correct
7 Incorrect 67 ms 5740 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 64 ms 5796 KB Output is correct
2 Correct 162 ms 25052 KB Output is correct
3 Correct 167 ms 25156 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 64 ms 5796 KB Output is correct
2 Correct 162 ms 25052 KB Output is correct
3 Correct 167 ms 25156 KB Output is correct
4 Incorrect 65 ms 5712 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 59 ms 5780 KB Output is correct
2 Correct 180 ms 30312 KB Output is correct
3 Correct 190 ms 30272 KB Output is correct
4 Correct 164 ms 30296 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5780 KB Output is correct
2 Correct 180 ms 30312 KB Output is correct
3 Correct 190 ms 30272 KB Output is correct
4 Correct 164 ms 30296 KB Output is correct
5 Incorrect 58 ms 5780 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 68 ms 5724 KB Output is correct
2 Correct 158 ms 25520 KB Output is correct
3 Correct 166 ms 25976 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 5724 KB Output is correct
2 Correct 158 ms 25520 KB Output is correct
3 Correct 166 ms 25976 KB Output is correct
4 Incorrect 64 ms 5740 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 60 ms 5708 KB Output is correct
2 Correct 179 ms 30408 KB Output is correct
3 Correct 173 ms 30384 KB Output is correct
4 Correct 170 ms 30192 KB Output is correct
5 Correct 65 ms 5708 KB Output is correct
6 Correct 155 ms 25548 KB Output is correct
7 Correct 178 ms 26012 KB Output is correct
8 Correct 209 ms 26392 KB Output is correct
9 Correct 183 ms 26428 KB Output is correct
10 Correct 209 ms 29628 KB Output is correct
11 Correct 248 ms 29160 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 5708 KB Output is correct
2 Correct 179 ms 30408 KB Output is correct
3 Correct 173 ms 30384 KB Output is correct
4 Correct 170 ms 30192 KB Output is correct
5 Correct 65 ms 5708 KB Output is correct
6 Correct 155 ms 25548 KB Output is correct
7 Correct 178 ms 26012 KB Output is correct
8 Correct 209 ms 26392 KB Output is correct
9 Correct 183 ms 26428 KB Output is correct
10 Correct 209 ms 29628 KB Output is correct
11 Correct 248 ms 29160 KB Output is correct
12 Incorrect 57 ms 5732 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 65 ms 5768 KB Output is correct
2 Correct 79 ms 6752 KB Output is correct
3 Correct 72 ms 6860 KB Output is correct
4 Correct 84 ms 6896 KB Output is correct
5 Correct 72 ms 6948 KB Output is correct
6 Correct 76 ms 6840 KB Output is correct
7 Correct 64 ms 5768 KB Output is correct
8 Correct 160 ms 25108 KB Output is correct
9 Correct 157 ms 25140 KB Output is correct
10 Correct 58 ms 5704 KB Output is correct
11 Correct 173 ms 30428 KB Output is correct
12 Correct 176 ms 30260 KB Output is correct
13 Correct 161 ms 30156 KB Output is correct
14 Correct 65 ms 5720 KB Output is correct
15 Correct 167 ms 25480 KB Output is correct
16 Correct 157 ms 26060 KB Output is correct
17 Correct 204 ms 26408 KB Output is correct
18 Correct 190 ms 26448 KB Output is correct
19 Correct 199 ms 29616 KB Output is correct
20 Correct 245 ms 29132 KB Output is correct
21 Correct 172 ms 25708 KB Output is correct
22 Correct 160 ms 25708 KB Output is correct
23 Correct 165 ms 25924 KB Output is correct
24 Correct 176 ms 26116 KB Output is correct
25 Correct 186 ms 26764 KB Output is correct
26 Correct 173 ms 25556 KB Output is correct
27 Correct 160 ms 25480 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 5768 KB Output is correct
2 Correct 79 ms 6752 KB Output is correct
3 Correct 72 ms 6860 KB Output is correct
4 Correct 84 ms 6896 KB Output is correct
5 Correct 72 ms 6948 KB Output is correct
6 Correct 76 ms 6840 KB Output is correct
7 Correct 64 ms 5768 KB Output is correct
8 Correct 160 ms 25108 KB Output is correct
9 Correct 157 ms 25140 KB Output is correct
10 Correct 58 ms 5704 KB Output is correct
11 Correct 173 ms 30428 KB Output is correct
12 Correct 176 ms 30260 KB Output is correct
13 Correct 161 ms 30156 KB Output is correct
14 Correct 65 ms 5720 KB Output is correct
15 Correct 167 ms 25480 KB Output is correct
16 Correct 157 ms 26060 KB Output is correct
17 Correct 204 ms 26408 KB Output is correct
18 Correct 190 ms 26448 KB Output is correct
19 Correct 199 ms 29616 KB Output is correct
20 Correct 245 ms 29132 KB Output is correct
21 Correct 172 ms 25708 KB Output is correct
22 Correct 160 ms 25708 KB Output is correct
23 Correct 165 ms 25924 KB Output is correct
24 Correct 176 ms 26116 KB Output is correct
25 Correct 186 ms 26764 KB Output is correct
26 Correct 173 ms 25556 KB Output is correct
27 Correct 160 ms 25480 KB Output is correct
28 Incorrect 63 ms 5724 KB Extra information in the output file
29 Halted 0 ms 0 KB -