oj.uz

Submission #123266

# Submission time Handle Problem Language Result Execution time Memory
123266 2019-06-30T23:58:54 Z imyujin Highway Tolls (IOI18_highway) C++14
100 / 100
 343 ms 11412 KB 
#include "highway.h"
#include<vector>
#include<queue>
#include<bitset>

using namespace std;

#define MAXN 90005

typedef long long lint;
typedef pair<int, int> pii;

int N, M;
lint d;
int se;
vector<pii> ed[MAXN];
int da[MAXN], db[MAXN];
bitset<MAXN> chk;
int num[MAXN];

void bfs(int x, int dx[]) {
	queue<int> q;

	for(int i = 0; i < N; i++) dx[i] = -1;
	dx[x] = 0;
	q.push(x);
	while(!q.empty()) {
		int t = q.front();
		q.pop();
		for(auto a : ed[t]) if(dx[a.first] == -1) {
			dx[a.first] = dx[t] + 1;
			q.push(a.first);
		}
	}
}

int f(int x, int dx[], int dy[]) {
	queue<int> q;
	vector<int> con;

	for(int i = 0; i < N; i++) chk[i] = false;
	q.push(x);
	chk[x] = true;
	while(!q.empty()) {
		int t = q.front();
		q.pop();
		con.push_back(t);
		for(auto a : ed[t]) if(dx[a.first] < dy[a.first] && !chk[a.first]) {
			chk[a.first] = true;
			q.push(a.first);
		}
	}

	for(int i = 0; i < N; i++) num[i] = -1;
	for(int i = 0; i < con.size(); i++) num[con[i]] = i;

	/*
	for(auto a : con) printf("%d ", a);
	printf("\n");
	*/

	vector<int> w(M, 0);
	int s = 0, e = con.size() - 1;
	int m = (s + e) / 2;
	for(int i = m + 1; i <= e; i++) for(auto a : ed[con[i]]) w[a.second] = 1;
	while(s < e) {
		//printf("s = %d, e = %d\n", s, e);
		if(ask(w) == d) {
			e = m;
			m = (s + e) / 2;
			for(int i = m + 1; i <= e; i++) for(auto a : ed[con[i]]) w[a.second] = 1;
		}
		else {
			s = m + 1;
			m = (s + e) / 2;
			for(int i = s; i <= m; i++) for(auto a : ed[con[i]]) if(num[a.first] < i) w[a.second] = 0;
		}
	}
	return con[s];
}

void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
	N = n;
	M = U.size();
	vector<int> w(M, 0);

	for(int i = 0; i < M; i++) {
		ed[U[i]].push_back(make_pair(V[i], i));
		ed[V[i]].push_back(make_pair(U[i], i));
	}

	d = ask(w);
	int s = 0, e = M - 1, m = (M-1) / 2;
	for(int i = m + 1; i <= e; i++) w[i] = 1;
	while(s < e) {
		if(ask(w) != d) {
			s = m + 1;
			m = (s + e) / 2;
			for(int i = s; i <= m; i++) w[i] = 0;
		}
		else {
			e = m;
			m = (s + e) / 2;
			for(int i = m + 1; i <= e; i++) w[i] = 1;
		}
	}
	se = s;

	int alpha = U[se], beta = V[se];
	//printf("se=%d(%d, %d)\n", se, alpha, beta);
	bfs(alpha, da);
	bfs(beta, db);
	//for(int i = 0; i < N; i++) printf("[%d %d]\n", da[i], db[i]);
	answer(f(alpha, da, db), f(beta, db, da));
}

Compilation message

highway.cpp: In function 'int f(int, int*, int*)':
highway.cpp:55:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < con.size(); i++) num[con[i]] = i;
                 ~~^~~~~~~~~~~~

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 2516 KB Output is correct
3 Correct 4 ms 2428 KB Output is correct
4 Correct 4 ms 2508 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 4 ms 2512 KB Output is correct
7 Correct 4 ms 2428 KB Output is correct
8 Correct 4 ms 2424 KB Output is correct
9 Correct 4 ms 2428 KB Output is correct
10 Correct 4 ms 2516 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 2480 KB Output is correct
2 Correct 23 ms 3144 KB Output is correct
3 Correct 223 ms 9504 KB Output is correct
4 Correct 219 ms 9532 KB Output is correct
5 Correct 206 ms 9516 KB Output is correct
6 Correct 213 ms 9624 KB Output is correct
7 Correct 223 ms 9528 KB Output is correct
8 Correct 195 ms 9632 KB Output is correct
9 Correct 207 ms 9424 KB Output is correct
10 Correct 228 ms 9512 KB Output is correct
11 Correct 264 ms 8804 KB Output is correct
12 Correct 251 ms 8840 KB Output is correct
13 Correct 242 ms 8948 KB Output is correct
14 Correct 247 ms 8940 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3060 KB Output is correct
2 Correct 34 ms 3884 KB Output is correct
3 Correct 52 ms 4572 KB Output is correct
4 Correct 174 ms 8900 KB Output is correct
5 Correct 152 ms 8840 KB Output is correct
6 Correct 174 ms 8972 KB Output is correct
7 Correct 177 ms 8936 KB Output is correct
8 Correct 178 ms 9016 KB Output is correct
9 Correct 158 ms 8860 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2480 KB Output is correct
2 Correct 26 ms 3192 KB Output is correct
3 Correct 155 ms 8020 KB Output is correct
4 Correct 225 ms 9500 KB Output is correct
5 Correct 222 ms 9500 KB Output is correct
6 Correct 228 ms 9548 KB Output is correct
7 Correct 234 ms 9508 KB Output is correct
8 Correct 218 ms 9512 KB Output is correct
9 Correct 203 ms 9488 KB Output is correct
10 Correct 225 ms 9524 KB Output is correct
11 Correct 247 ms 8924 KB Output is correct
12 Correct 294 ms 8888 KB Output is correct
13 Correct 272 ms 8956 KB Output is correct
14 Correct 270 ms 8824 KB Output is correct
15 Correct 201 ms 9524 KB Output is correct
16 Correct 207 ms 9632 KB Output is correct
17 Correct 267 ms 8916 KB Output is correct
18 Correct 229 ms 9128 KB Output is correct
19 Correct 235 ms 9604 KB Output is correct
20 Correct 232 ms 9000 KB Output is correct
21 Correct 166 ms 10060 KB Output is correct
22 Correct 181 ms 10040 KB Output is correct
23 Correct 210 ms 9828 KB Output is correct
24 Correct 225 ms 9688 KB Output is correct
25 Correct 247 ms 9016 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3224 KB Output is correct
2 Correct 29 ms 3384 KB Output is correct
3 Correct 239 ms 9732 KB Output is correct
4 Correct 252 ms 10560 KB Output is correct
5 Correct 301 ms 11304 KB Output is correct
6 Correct 322 ms 11328 KB Output is correct
7 Correct 317 ms 11344 KB Output is correct
8 Correct 301 ms 11320 KB Output is correct
9 Correct 246 ms 9172 KB Output is correct
10 Correct 231 ms 9552 KB Output is correct
11 Correct 280 ms 10052 KB Output is correct
12 Correct 301 ms 10740 KB Output is correct
13 Correct 309 ms 11164 KB Output is correct
14 Correct 334 ms 11328 KB Output is correct
15 Correct 343 ms 11412 KB Output is correct
16 Correct 281 ms 9976 KB Output is correct
17 Correct 207 ms 10068 KB Output is correct
18 Correct 203 ms 10240 KB Output is correct
19 Correct 216 ms 10240 KB Output is correct
20 Correct 201 ms 10144 KB Output is correct
21 Correct 285 ms 11412 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3456 KB Output is correct
2 Correct 28 ms 3184 KB Output is correct
3 Correct 247 ms 10004 KB Output is correct
4 Correct 250 ms 10032 KB Output is correct
5 Correct 284 ms 10212 KB Output is correct
6 Correct 304 ms 11280 KB Output is correct
7 Correct 251 ms 9940 KB Output is correct
8 Correct 287 ms 10084 KB Output is correct
9 Correct 265 ms 10436 KB Output is correct
10 Correct 309 ms 11408 KB Output is correct
11 Correct 301 ms 11412 KB Output is correct
12 Correct 309 ms 11336 KB Output is correct
13 Correct 260 ms 10040 KB Output is correct
14 Correct 259 ms 9568 KB Output is correct
15 Correct 261 ms 10024 KB Output is correct
16 Correct 225 ms 9532 KB Output is correct
17 Correct 301 ms 10020 KB Output is correct
18 Correct 234 ms 9600 KB Output is correct
19 Correct 295 ms 10812 KB Output is correct
20 Correct 286 ms 11140 KB Output is correct
21 Correct 330 ms 11348 KB Output is correct
22 Correct 313 ms 11348 KB Output is correct
23 Correct 324 ms 11288 KB Output is correct
24 Correct 308 ms 11256 KB Output is correct
25 Correct 315 ms 11300 KB Output is correct
26 Correct 319 ms 11380 KB Output is correct
27 Correct 199 ms 10332 KB Output is correct
28 Correct 216 ms 10116 KB Output is correct
29 Correct 199 ms 10484 KB Output is correct
30 Correct 210 ms 10220 KB Output is correct
31 Correct 205 ms 10256 KB Output is correct
32 Correct 197 ms 10088 KB Output is correct
33 Correct 198 ms 10360 KB Output is correct
34 Correct 209 ms 10144 KB Output is correct
35 Correct 190 ms 10148 KB Output is correct
36 Correct 200 ms 10124 KB Output is correct
37 Correct 221 ms 10384 KB Output is correct
38 Correct 195 ms 10264 KB Output is correct
39 Correct 299 ms 11404 KB Output is correct
40 Correct 335 ms 11392 KB Output is correct
41 Correct 313 ms 11380 KB Output is correct
42 Correct 320 ms 11396 KB Output is correct