oj.uz

Submission #122358

# Submission time Handle Problem Language Result Execution time Memory
122358 2019-06-28T05:37:00 Z tmwilliamlin168 Highway Tolls (IOI18_highway) C++14
100 / 100
 379 ms 14996 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN=9e4;
int m, d1[mxN], d2[mxN], me;
vector<int> eu, ev, adj[mxN];
vector<array<int, 2>> p1, p2;
long long bc;

void bfs(int s, int d[mxN], vector<array<int, 2>> &p) {
	memset(d, 0x3f, 4*mxN);
	d[s]=0;
	p.push_back({s});
	for(int qh=0; qh<p.size(); ++qh) {
		int u=p[qh][0];
		for(int e : adj[u]) {
			int v=eu[e]^ev[e]^u;
			if(d[v]>d[u]+1) {
				d[v]=d[u]+1;
				p.push_back({v, e});
			}
		}
	}
}

int solve(int d1[mxN], int d2[mxN], vector<array<int, 2>> p1, vector<array<int, 2>> p2) {
	vector<array<int, 2>> q;
	for(array<int, 2> a : p1)
		if(d1[a[0]]<d2[a[0]])
			q.push_back(a);//, cout << a[0] << " " << a[1] << endl;
	int lb=0, rb=q.size()-1;
	while(lb<rb) {
		int mb=(lb+rb+1)/2;
		vector<int> w(m, 1);
		w[me]=0;
		for(int i=0; i<mb; ++i)
			w[q[i][1]]=0;
		for(array<int, 2> a : p2)
			if(d2[a[0]]<d1[a[0]])
				w[a[1]]=0;
		if(ask(w)>bc)
			lb=mb;
		else
			rb=mb-1;
	}
	return q[lb][0];
}

void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
	eu=u;
	ev=v;
	m=u.size();
	for(int i=0; i<m; ++i) {
		adj[u[i]].push_back(i);
		adj[v[i]].push_back(i);
	}
	bc=ask(vector<int>(m));
	int lb=0, rb=m-1;
	while(lb<rb) {
		int mb=(lb+rb)/2;
		vector<int> w(m);
		fill(w.begin(), w.begin()+mb+1, 1);
		if(ask(w)>bc)
			rb=mb;
		else
			lb=mb+1;
	}
	me=lb;
	//cout << lb << endl;
	bfs(u[me], d1, p1);
	bfs(v[me], d2, p2);
	answer(solve(d1, d2, p1, p2), solve(d2, d1, p2, p1));
}

Compilation message

highway.cpp: In function 'void bfs(int, int*, std::vector<std::array<int, 2> >&)':
highway.cpp:15:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int qh=0; qh<p.size(); ++qh) {
                ~~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB Output is correct
2 Correct 4 ms 3092 KB Output is correct
3 Correct 4 ms 3172 KB Output is correct
4 Correct 4 ms 3172 KB Output is correct
5 Correct 4 ms 3080 KB Output is correct
6 Correct 5 ms 3168 KB Output is correct
7 Correct 4 ms 3084 KB Output is correct
8 Correct 5 ms 3168 KB Output is correct
9 Correct 4 ms 3112 KB Output is correct
10 Correct 5 ms 3064 KB Output is correct
11 Correct 4 ms 3088 KB Output is correct
12 Correct 5 ms 3068 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3140 KB Output is correct
2 Correct 26 ms 4292 KB Output is correct
3 Correct 243 ms 13936 KB Output is correct
4 Correct 230 ms 12812 KB Output is correct
5 Correct 239 ms 12716 KB Output is correct
6 Correct 223 ms 12452 KB Output is correct
7 Correct 248 ms 12816 KB Output is correct
8 Correct 228 ms 12700 KB Output is correct
9 Correct 224 ms 13944 KB Output is correct
10 Correct 258 ms 12772 KB Output is correct
11 Correct 269 ms 13264 KB Output is correct
12 Correct 258 ms 13948 KB Output is correct
13 Correct 257 ms 12752 KB Output is correct
14 Correct 254 ms 13796 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 4244 KB Output is correct
2 Correct 26 ms 5360 KB Output is correct
3 Correct 56 ms 6676 KB Output is correct
4 Correct 170 ms 13092 KB Output is correct
5 Correct 181 ms 13116 KB Output is correct
6 Correct 179 ms 13152 KB Output is correct
7 Correct 176 ms 13840 KB Output is correct
8 Correct 158 ms 13380 KB Output is correct
9 Correct 184 ms 13748 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3144 KB Output is correct
2 Correct 28 ms 4276 KB Output is correct
3 Correct 145 ms 10816 KB Output is correct
4 Correct 212 ms 12768 KB Output is correct
5 Correct 228 ms 13864 KB Output is correct
6 Correct 215 ms 12508 KB Output is correct
7 Correct 219 ms 14012 KB Output is correct
8 Correct 208 ms 13900 KB Output is correct
9 Correct 249 ms 13948 KB Output is correct
10 Correct 254 ms 13864 KB Output is correct
11 Correct 241 ms 13860 KB Output is correct
12 Correct 279 ms 12912 KB Output is correct
13 Correct 246 ms 13824 KB Output is correct
14 Correct 262 ms 13316 KB Output is correct
15 Correct 241 ms 12688 KB Output is correct
16 Correct 217 ms 12520 KB Output is correct
17 Correct 264 ms 13832 KB Output is correct
18 Correct 252 ms 13760 KB Output is correct
19 Correct 220 ms 13912 KB Output is correct
20 Correct 256 ms 12996 KB Output is correct
21 Correct 202 ms 12700 KB Output is correct
22 Correct 200 ms 14232 KB Output is correct
23 Correct 221 ms 13548 KB Output is correct
24 Correct 227 ms 13532 KB Output is correct
25 Correct 258 ms 13888 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4220 KB Output is correct
2 Correct 25 ms 4380 KB Output is correct
3 Correct 267 ms 13140 KB Output is correct
4 Correct 298 ms 13940 KB Output is correct
5 Correct 307 ms 14272 KB Output is correct
6 Correct 325 ms 14304 KB Output is correct
7 Correct 356 ms 14612 KB Output is correct
8 Correct 379 ms 14576 KB Output is correct
9 Correct 247 ms 10056 KB Output is correct
10 Correct 244 ms 10120 KB Output is correct
11 Correct 265 ms 11016 KB Output is correct
12 Correct 312 ms 13216 KB Output is correct
13 Correct 339 ms 13856 KB Output is correct
14 Correct 343 ms 14468 KB Output is correct
15 Correct 332 ms 14428 KB Output is correct
16 Correct 293 ms 11192 KB Output is correct
17 Correct 225 ms 14444 KB Output is correct
18 Correct 214 ms 13276 KB Output is correct
19 Correct 242 ms 14224 KB Output is correct
20 Correct 215 ms 13380 KB Output is correct
21 Correct 334 ms 14264 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4280 KB Output is correct
2 Correct 25 ms 4384 KB Output is correct
3 Correct 265 ms 13732 KB Output is correct
4 Correct 249 ms 13672 KB Output is correct
5 Correct 293 ms 13644 KB Output is correct
6 Correct 335 ms 14368 KB Output is correct
7 Correct 240 ms 13200 KB Output is correct
8 Correct 276 ms 13352 KB Output is correct
9 Correct 299 ms 13804 KB Output is correct
10 Correct 337 ms 14496 KB Output is correct
11 Correct 315 ms 14360 KB Output is correct
12 Correct 348 ms 14408 KB Output is correct
13 Correct 257 ms 10568 KB Output is correct
14 Correct 253 ms 10500 KB Output is correct
15 Correct 241 ms 10596 KB Output is correct
16 Correct 256 ms 10540 KB Output is correct
17 Correct 285 ms 10584 KB Output is correct
18 Correct 242 ms 10076 KB Output is correct
19 Correct 294 ms 13192 KB Output is correct
20 Correct 324 ms 13820 KB Output is correct
21 Correct 326 ms 14392 KB Output is correct
22 Correct 351 ms 14372 KB Output is correct
23 Correct 327 ms 14228 KB Output is correct
24 Correct 341 ms 14448 KB Output is correct
25 Correct 337 ms 14384 KB Output is correct
26 Correct 334 ms 14376 KB Output is correct
27 Correct 230 ms 14316 KB Output is correct
28 Correct 230 ms 13184 KB Output is correct
29 Correct 219 ms 14424 KB Output is correct
30 Correct 224 ms 14272 KB Output is correct
31 Correct 175 ms 14300 KB Output is correct
32 Correct 233 ms 14160 KB Output is correct
33 Correct 228 ms 13320 KB Output is correct
34 Correct 247 ms 14296 KB Output is correct
35 Correct 216 ms 14268 KB Output is correct
36 Correct 208 ms 13148 KB Output is correct
37 Correct 229 ms 14484 KB Output is correct
38 Correct 220 ms 13036 KB Output is correct
39 Correct 345 ms 14412 KB Output is correct
40 Correct 330 ms 14996 KB Output is correct
41 Correct 311 ms 14012 KB Output is correct
42 Correct 275 ms 14484 KB Output is correct