oj.uz

Submission #158279

# Submission time Handle Problem Language Result Execution time Memory
158279 2019-10-16T02:13:10 Z kig9981 Highway Tolls (IOI18_highway) C++17
51 / 100
 1500 ms 9160 KB 
#include "highway.h"
#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> adj[90000];
int dist1[90000], dist2[90000];
bool chk[90000];
 
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
	int M=U.size(), S, T, s, e, E;
	vector<int> W(M,0), C1, C2;
	queue<int> Q;
	long long D=ask(W);
	for(int i=0;i<M;i++) {
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}
	s=0; e=N-1;
	while(s<=e) {
		int m=(s+e)>>1;
		for(int i=0;i<M;i++) W[i]=i<=m;
		if(ask(W)!=D) e=m-1;
		else s=m+1;
	}
	E=s;
	memset(dist1,0x7f,sizeof(dist1));
	memset(dist2,0x7f,sizeof(dist2));
	dist1[U[E]]=0; Q.push(U[E]);
	while(!Q.empty()) {
		int c=Q.front();
		Q.pop();
		for(auto n: adj[c]) if(dist1[n]>dist1[c]+1) {
			dist1[n]=dist1[c]+1;
			Q.push(n);
		}
	}
	dist2[V[E]]=0; Q.push(V[E]);
	while(!Q.empty()) {
		int c=Q.front();
		Q.pop();
		for(auto n: adj[c]) if(dist2[n]>dist2[c]+1) {
			dist2[n]=dist2[c]+1;
			Q.push(n);
		}
	}
	s=0; e=D/A-1;
	while(s<=e) {
		int m=(s+e)>>1;
		for(int i=0;i<M;i++) W[i]=(dist1[U[i]]<dist2[U[i]] && dist1[U[i]]>=m)^(dist1[V[i]]<dist2[V[i]] && dist1[V[i]]>=m);
		if(ask(W)!=D) s=m+1;
		else e=m-1;
	}
  while(0>e && e>=D/A);
	for(int i=0;i<N;i++) {
		if(dist1[i]<dist2[i] && dist1[i]==e) C1.push_back(i);
		if(dist1[i]>dist2[i] && dist2[i]==D/A-s) C2.push_back(i);
		chk[i]=false;
	}
  while(C1.empty() || C2.empty());
	s=0; e=C1.size()-1;
	while(s<=e) {
		int m=(s+e)>>1;
		for(int i=0;i<N;i++) chk[i]=false;
		for(int i=0;i<=m;i++) chk[C1[i]]=true;
		for(int i=0;i<M;i++) W[i]=chk[U[i]]^chk[V[i]];
		if(ask(W)!=D) e=m-1;
		else s=m+1;
	}
  //while(0>s && s>=C1.size());
	S=C1[s];
	s=0; e=C2.size()-1;
	while(s<=e) {
		int m=(s+e)>>1;
		for(int i=0;i<N;i++) chk[i]=false;
		for(int i=0;i<=m;i++) chk[C2[i]]=true;
		for(int i=0;i<M;i++) W[i]=chk[U[i]]^chk[V[i]];
		if(ask(W)!=D) e=m-1;
		else s=m+1;
	}
  //while(0>s && s>=C2.size());
	T=C2[s];
	answer(S,T);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:55:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(0>e && e>=D/A);
   ^~~~~
highway.cpp:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  for(int i=0;i<N;i++) {
  ^~~
highway.cpp:61:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(C1.empty() || C2.empty());
   ^~~~~
highway.cpp:62:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  s=0; e=C1.size()-1;
  ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3076 KB Output is correct
2 Correct 4 ms 3192 KB Output is correct
3 Correct 4 ms 3064 KB Output is correct
4 Correct 4 ms 3064 KB Output is correct
5 Correct 4 ms 3192 KB Output is correct
6 Correct 4 ms 3064 KB Output is correct
7 Correct 4 ms 3064 KB Output is correct
8 Correct 4 ms 3064 KB Output is correct
9 Correct 4 ms 3084 KB Output is correct
10 Correct 5 ms 3112 KB Output is correct
11 Correct 4 ms 3076 KB Output is correct
12 Correct 4 ms 3064 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3192 KB Output is correct
2 Correct 25 ms 3576 KB Output is correct
3 Correct 208 ms 8140 KB Output is correct
4 Correct 196 ms 8032 KB Output is correct
5 Correct 199 ms 8052 KB Output is correct
6 Correct 205 ms 7960 KB Output is correct
7 Correct 184 ms 8044 KB Output is correct
8 Correct 215 ms 7968 KB Output is correct
9 Correct 178 ms 8000 KB Output is correct
10 Correct 210 ms 8044 KB Output is correct
11 Correct 219 ms 7832 KB Output is correct
12 Correct 223 ms 7908 KB Output is correct
13 Correct 210 ms 7736 KB Output is correct
14 Correct 219 ms 7728 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3576 KB Output is correct
2 Correct 41 ms 4088 KB Output is correct
3 Correct 57 ms 4604 KB Output is correct
4 Correct 164 ms 7824 KB Output is correct
5 Correct 183 ms 7744 KB Output is correct
6 Correct 170 ms 7732 KB Output is correct
7 Correct 156 ms 7796 KB Output is correct
8 Correct 172 ms 7720 KB Output is correct
9 Correct 169 ms 7896 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3192 KB Output is correct
2 Correct 25 ms 3576 KB Output is correct
3 Correct 148 ms 6820 KB Output is correct
4 Correct 198 ms 7988 KB Output is correct
5 Correct 188 ms 7900 KB Output is correct
6 Correct 206 ms 8040 KB Output is correct
7 Correct 167 ms 7864 KB Output is correct
8 Correct 174 ms 7868 KB Output is correct
9 Correct 217 ms 8160 KB Output is correct
10 Correct 210 ms 8048 KB Output is correct
11 Correct 245 ms 7740 KB Output is correct
12 Correct 215 ms 7732 KB Output is correct
13 Correct 202 ms 7816 KB Output is correct
14 Correct 216 ms 7800 KB Output is correct
15 Correct 191 ms 7864 KB Output is correct
16 Correct 191 ms 7928 KB Output is correct
17 Correct 216 ms 7732 KB Output is correct
18 Correct 203 ms 7792 KB Output is correct
19 Correct 193 ms 7968 KB Output is correct
20 Correct 199 ms 7816 KB Output is correct
21 Correct 198 ms 9160 KB Output is correct
22 Correct 193 ms 9148 KB Output is correct
23 Correct 218 ms 8992 KB Output is correct
24 Correct 209 ms 8860 KB Output is correct
25 Correct 227 ms 7984 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3692 KB Output is correct
2 Correct 28 ms 3704 KB Output is correct
3 Correct 222 ms 8272 KB Output is correct
4 Correct 247 ms 8540 KB Output is correct
5 Correct 281 ms 9092 KB Output is correct
6 Correct 275 ms 9016 KB Output is correct
7 Correct 279 ms 9080 KB Output is correct
8 Correct 286 ms 8992 KB Output is correct
9 Execution timed out 3049 ms 7452 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3684 KB Output is correct
2 Correct 22 ms 3704 KB Output is correct
3 Correct 226 ms 8224 KB Output is correct
4 Correct 239 ms 8356 KB Output is correct
5 Correct 257 ms 8636 KB Output is correct
6 Correct 286 ms 9020 KB Output is correct
7 Correct 233 ms 8304 KB Output is correct
8 Correct 229 ms 8420 KB Output is correct
9 Correct 242 ms 8692 KB Output is correct
10 Correct 282 ms 9096 KB Output is correct
11 Correct 269 ms 9000 KB Output is correct
12 Correct 281 ms 9052 KB Output is correct
13 Execution timed out 3077 ms 7872 KB Time limit exceeded
14 Halted 0 ms 0 KB -