oj.uz

Submission #169883

# Submission time Handle Problem Language Result Execution time Memory
169883 2019-12-23T06:50:06 Z dennisstar Highway Tolls (IOI18_highway) C++11
100 / 100
 373 ms 10308 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;

vim G[90010];
int chk[90010];

void find_pair(int N, vim U, vim V, int A, int B) {
	int M=U.size();
	vim w(M);
	ll L=ask(w);

	for (int i=0; i<M; i++) G[U[i]].push_back(V[i]), G[V[i]].push_back(U[i]);

	int s, e;
	for (s=0, e=M-1; s<e; ) {
		int m=(s+e)/2;
		fill(w.begin(), w.begin()+m+1, 1);
		fill(w.begin()+m+1, w.end(), 0);
		if (L!=ask(w)) e=m;
		else s=m+1;
	}

	vector<pii> stk; vector<int> ar[2];
	stk.push_back({0, U[s]}); stk.push_back({1, V[s]});
	chk[U[s]]=chk[V[s]]=1;
	for (int i=0; i<stk.size(); i++) {
		ar[stk[i].fi].push_back(stk[i].se);
		for (int j:G[stk[i].se]) {
			if (chk[j]) continue;
			chk[j]=1;
			stk.push_back({stk[i].fi, j});
		}
	}

	int S, T;
	for (s=0, e=ar[0].size()-1; s<e; ) {
		int m=(s+e+1)/2;
		vim X(N);
		fill(w.begin(), w.end(), 0);
		for (int i=m; i<ar[0].size(); i++) X[ar[0][i]]=1;
		for (int i=0; i<M; i++) {
			if (X[U[i]]!=X[V[i]]) w[i]=1;
		}
		if (L!=ask(w)) s=m;
		else e=m-1;
	}
	S=ar[0][s];

	for (s=0, e=ar[1].size()-1; s<e; ) {
		int m=(s+e+1)/2;
		vim X(N);
		fill(w.begin(), w.end(), 0);
		for (int i=m; i<ar[1].size(); i++) X[ar[1][i]]=1;
		for (int i=0; i<M; i++) {
			if (X[U[i]]!=X[V[i]]) w[i]=1;
		}
		if (L!=ask(w)) s=m;
		else e=m-1;
	}
	T=ar[1][s];

	answer(S, T);
}

Compilation message

highway.cpp: In function 'void find_pair(int, vim, vim, int, int)':
highway.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<stk.size(); i++) {
                ~^~~~~~~~~~~
highway.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=m; i<ar[0].size(); i++) X[ar[0][i]]=1;
                 ~^~~~~~~~~~~~~
highway.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=m; i<ar[1].size(); i++) X[ar[1][i]]=1;
                 ~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 4 ms 2424 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2428 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 4 ms 2424 KB Output is correct
9 Correct 4 ms 2424 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 4 ms 2424 KB Output is correct
12 Correct 4 ms 2424 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 19 ms 3064 KB Output is correct
3 Correct 212 ms 9112 KB Output is correct
4 Correct 221 ms 9056 KB Output is correct
5 Correct 222 ms 9072 KB Output is correct
6 Correct 209 ms 9060 KB Output is correct
7 Correct 207 ms 9132 KB Output is correct
8 Correct 224 ms 9084 KB Output is correct
9 Correct 214 ms 9108 KB Output is correct
10 Correct 217 ms 9000 KB Output is correct
11 Correct 231 ms 9112 KB Output is correct
12 Correct 222 ms 9324 KB Output is correct
13 Correct 224 ms 9004 KB Output is correct
14 Correct 222 ms 9080 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3188 KB Output is correct
2 Correct 40 ms 3952 KB Output is correct
3 Correct 60 ms 4688 KB Output is correct
4 Correct 201 ms 9132 KB Output is correct
5 Correct 174 ms 9072 KB Output is correct
6 Correct 172 ms 9380 KB Output is correct
7 Correct 178 ms 9064 KB Output is correct
8 Correct 179 ms 8980 KB Output is correct
9 Correct 170 ms 9032 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 29 ms 3080 KB Output is correct
3 Correct 157 ms 8028 KB Output is correct
4 Correct 207 ms 9060 KB Output is correct
5 Correct 204 ms 9044 KB Output is correct
6 Correct 203 ms 9008 KB Output is correct
7 Correct 210 ms 9048 KB Output is correct
8 Correct 199 ms 9044 KB Output is correct
9 Correct 234 ms 9160 KB Output is correct
10 Correct 218 ms 9084 KB Output is correct
11 Correct 235 ms 9068 KB Output is correct
12 Correct 223 ms 9100 KB Output is correct
13 Correct 242 ms 8808 KB Output is correct
14 Correct 240 ms 9012 KB Output is correct
15 Correct 215 ms 9064 KB Output is correct
16 Correct 202 ms 9036 KB Output is correct
17 Correct 236 ms 9004 KB Output is correct
18 Correct 224 ms 8976 KB Output is correct
19 Correct 200 ms 9064 KB Output is correct
20 Correct 216 ms 8876 KB Output is correct
21 Correct 182 ms 9316 KB Output is correct
22 Correct 185 ms 9336 KB Output is correct
23 Correct 192 ms 9412 KB Output is correct
24 Correct 202 ms 9468 KB Output is correct
25 Correct 225 ms 9120 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3268 KB Output is correct
2 Correct 26 ms 3292 KB Output is correct
3 Correct 242 ms 9280 KB Output is correct
4 Correct 279 ms 9848 KB Output is correct
5 Correct 353 ms 10308 KB Output is correct
6 Correct 332 ms 10188 KB Output is correct
7 Correct 333 ms 10240 KB Output is correct
8 Correct 308 ms 10172 KB Output is correct
9 Correct 258 ms 7404 KB Output is correct
10 Correct 259 ms 7628 KB Output is correct
11 Correct 269 ms 7828 KB Output is correct
12 Correct 309 ms 9520 KB Output is correct
13 Correct 326 ms 9612 KB Output is correct
14 Correct 326 ms 9852 KB Output is correct
15 Correct 310 ms 9856 KB Output is correct
16 Correct 286 ms 8268 KB Output is correct
17 Correct 216 ms 9472 KB Output is correct
18 Correct 211 ms 9556 KB Output is correct
19 Correct 203 ms 9496 KB Output is correct
20 Correct 208 ms 9488 KB Output is correct
21 Correct 278 ms 9996 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3220 KB Output is correct
2 Correct 25 ms 3252 KB Output is correct
3 Correct 257 ms 9600 KB Output is correct
4 Correct 269 ms 9672 KB Output is correct
5 Correct 274 ms 9644 KB Output is correct
6 Correct 321 ms 10136 KB Output is correct
7 Correct 236 ms 9336 KB Output is correct
8 Correct 251 ms 9392 KB Output is correct
9 Correct 274 ms 9672 KB Output is correct
10 Correct 373 ms 9968 KB Output is correct
11 Correct 348 ms 10268 KB Output is correct
12 Correct 344 ms 10168 KB Output is correct
13 Correct 269 ms 7916 KB Output is correct
14 Correct 267 ms 7640 KB Output is correct
15 Correct 242 ms 7960 KB Output is correct
16 Correct 244 ms 7592 KB Output is correct
17 Correct 280 ms 7844 KB Output is correct
18 Correct 246 ms 7532 KB Output is correct
19 Correct 332 ms 9352 KB Output is correct
20 Correct 357 ms 9652 KB Output is correct
21 Correct 318 ms 10108 KB Output is correct
22 Correct 336 ms 10084 KB Output is correct
23 Correct 316 ms 10152 KB Output is correct
24 Correct 320 ms 10168 KB Output is correct
25 Correct 312 ms 10252 KB Output is correct
26 Correct 322 ms 10212 KB Output is correct
27 Correct 200 ms 9576 KB Output is correct
28 Correct 224 ms 9392 KB Output is correct
29 Correct 199 ms 9536 KB Output is correct
30 Correct 212 ms 9548 KB Output is correct
31 Correct 233 ms 9472 KB Output is correct
32 Correct 225 ms 9444 KB Output is correct
33 Correct 225 ms 9532 KB Output is correct
34 Correct 204 ms 9452 KB Output is correct
35 Correct 219 ms 9484 KB Output is correct
36 Correct 208 ms 9552 KB Output is correct
37 Correct 219 ms 9716 KB Output is correct
38 Correct 211 ms 9560 KB Output is correct
39 Correct 312 ms 10084 KB Output is correct
40 Correct 309 ms 10020 KB Output is correct
41 Correct 299 ms 10080 KB Output is correct
42 Correct 281 ms 10072 KB Output is correct