oj.uz

Submission #158298

# Submission time Handle Problem Language Result Execution time Memory
158298 2019-10-16T05:22:13 Z kig9981 Highway Tolls (IOI18_highway) C++17
100 / 100
 351 ms 9480 KB 
#include "highway.h"
#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> adj[90000];
int dist[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;
	vector<int> W(M), C1, C2;
	queue<pair<int,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=M-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;
	}
	memset(dist,0x7f,sizeof(dist));
	dist[U[s]]=dist[V[s]]=0;
	Q.emplace(0,U[s]);
	Q.emplace(1,V[s]);
	while(!Q.empty()) {
		auto[v,c]=Q.front();
		Q.pop();
		(v ? C1:C2).push_back(c);
		for(auto n: adj[c]) if(dist[n]>dist[c]+1) {
			dist[n]=dist[c]+1;
			Q.emplace(v,n);
		}
	}
	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=m;i<C1.size();i++) chk[C1[i]]=true;
		for(int i=0;i<M;i++) W[i]=chk[U[i]]^chk[V[i]];
		if(ask(W)!=D) s=m+1;
		else e=m-1;
	}
	S=C1[e];
	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=m;i<C2.size();i++) chk[C2[i]]=true;
		for(int i=0;i<M;i++) W[i]=chk[U[i]]^chk[V[i]];
		if(ask(W)!=D) s=m+1;
		else e=m-1;
	}
	T=C2[e];
  assert(S!=T);
	answer(S,T);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=m;i<C1.size();i++) chk[C1[i]]=true;
               ~^~~~~~~~~~
highway.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=m;i<C2.size();i++) chk[C2[i]]=true;
               ~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2776 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 4 ms 2728 KB Output is correct
9 Correct 4 ms 2684 KB Output is correct
10 Correct 4 ms 2696 KB Output is correct
11 Correct 4 ms 2808 KB Output is correct
12 Correct 4 ms 2692 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 24 ms 3448 KB Output is correct
3 Correct 204 ms 8120 KB Output is correct
4 Correct 201 ms 8128 KB Output is correct
5 Correct 195 ms 8112 KB Output is correct
6 Correct 188 ms 8064 KB Output is correct
7 Correct 204 ms 8080 KB Output is correct
8 Correct 204 ms 8152 KB Output is correct
9 Correct 202 ms 8052 KB Output is correct
10 Correct 181 ms 8116 KB Output is correct
11 Correct 212 ms 7952 KB Output is correct
12 Correct 202 ms 8140 KB Output is correct
13 Correct 230 ms 7960 KB Output is correct
14 Correct 256 ms 7988 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3320 KB Output is correct
2 Correct 40 ms 3924 KB Output is correct
3 Correct 58 ms 4488 KB Output is correct
4 Correct 170 ms 7892 KB Output is correct
5 Correct 167 ms 7924 KB Output is correct
6 Correct 189 ms 8232 KB Output is correct
7 Correct 178 ms 8096 KB Output is correct
8 Correct 178 ms 8056 KB Output is correct
9 Correct 191 ms 8112 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 28 ms 3368 KB Output is correct
3 Correct 172 ms 7144 KB Output is correct
4 Correct 198 ms 8116 KB Output is correct
5 Correct 204 ms 8112 KB Output is correct
6 Correct 196 ms 8068 KB Output is correct
7 Correct 202 ms 8152 KB Output is correct
8 Correct 196 ms 8064 KB Output is correct
9 Correct 198 ms 8292 KB Output is correct
10 Correct 198 ms 8252 KB Output is correct
11 Correct 200 ms 8036 KB Output is correct
12 Correct 177 ms 8184 KB Output is correct
13 Correct 202 ms 8052 KB Output is correct
14 Correct 205 ms 7840 KB Output is correct
15 Correct 175 ms 8068 KB Output is correct
16 Correct 194 ms 8132 KB Output is correct
17 Correct 209 ms 8052 KB Output is correct
18 Correct 212 ms 8132 KB Output is correct
19 Correct 198 ms 8092 KB Output is correct
20 Correct 198 ms 8008 KB Output is correct
21 Correct 162 ms 9240 KB Output is correct
22 Correct 178 ms 9148 KB Output is correct
23 Correct 191 ms 8688 KB Output is correct
24 Correct 193 ms 8644 KB Output is correct
25 Correct 208 ms 8084 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3368 KB Output is correct
2 Correct 41 ms 3440 KB Output is correct
3 Correct 211 ms 8376 KB Output is correct
4 Correct 235 ms 8812 KB Output is correct
5 Correct 286 ms 9340 KB Output is correct
6 Correct 286 ms 9480 KB Output is correct
7 Correct 300 ms 9388 KB Output is correct
8 Correct 300 ms 9260 KB Output is correct
9 Correct 249 ms 7508 KB Output is correct
10 Correct 253 ms 7864 KB Output is correct
11 Correct 247 ms 8196 KB Output is correct
12 Correct 289 ms 8916 KB Output is correct
13 Correct 267 ms 9124 KB Output is correct
14 Correct 291 ms 9084 KB Output is correct
15 Correct 266 ms 9052 KB Output is correct
16 Correct 298 ms 8256 KB Output is correct
17 Correct 197 ms 9060 KB Output is correct
18 Correct 201 ms 9320 KB Output is correct
19 Correct 189 ms 9212 KB Output is correct
20 Correct 204 ms 9240 KB Output is correct
21 Correct 288 ms 9048 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3448 KB Output is correct
2 Correct 29 ms 3448 KB Output is correct
3 Correct 233 ms 8516 KB Output is correct
4 Correct 240 ms 8600 KB Output is correct
5 Correct 255 ms 8792 KB Output is correct
6 Correct 294 ms 9416 KB Output is correct
7 Correct 223 ms 8396 KB Output is correct
8 Correct 256 ms 8496 KB Output is correct
9 Correct 249 ms 8756 KB Output is correct
10 Correct 285 ms 9228 KB Output is correct
11 Correct 301 ms 9268 KB Output is correct
12 Correct 298 ms 9344 KB Output is correct
13 Correct 255 ms 8048 KB Output is correct
14 Correct 254 ms 7912 KB Output is correct
15 Correct 253 ms 8068 KB Output is correct
16 Correct 252 ms 7860 KB Output is correct
17 Correct 257 ms 8024 KB Output is correct
18 Correct 251 ms 7836 KB Output is correct
19 Correct 279 ms 8756 KB Output is correct
20 Correct 288 ms 8972 KB Output is correct
21 Correct 351 ms 9088 KB Output is correct
22 Correct 277 ms 9144 KB Output is correct
23 Correct 278 ms 9176 KB Output is correct
24 Correct 288 ms 9100 KB Output is correct
25 Correct 285 ms 9192 KB Output is correct
26 Correct 294 ms 9096 KB Output is correct
27 Correct 196 ms 9276 KB Output is correct
28 Correct 200 ms 9180 KB Output is correct
29 Correct 191 ms 9392 KB Output is correct
30 Correct 195 ms 8800 KB Output is correct
31 Correct 208 ms 9208 KB Output is correct
32 Correct 192 ms 9052 KB Output is correct
33 Correct 207 ms 9368 KB Output is correct
34 Correct 225 ms 9220 KB Output is correct
35 Correct 198 ms 9240 KB Output is correct
36 Correct 209 ms 9088 KB Output is correct
37 Correct 187 ms 9204 KB Output is correct
38 Correct 203 ms 9188 KB Output is correct
39 Correct 275 ms 8996 KB Output is correct
40 Correct 287 ms 9112 KB Output is correct
41 Correct 275 ms 9072 KB Output is correct
42 Correct 290 ms 8960 KB Output is correct