oj.uz

Submission #122351

# Submission time Handle Problem Language Result Execution time Memory
122351 2019-06-28T05:24:42 Z tmwilliamlin168 Highway Tolls (IOI18_highway) C++14
51 / 100
 328 ms 14088 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN=9e4;
int m, d1[mxN], d2[mxN];
vector<int> eu, ev, adj[mxN], bv;
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>> p) {
	vector<array<int, 2>> q;
	for(array<int, 2> a : p)
		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=bv;
		for(int i=mb; i<q.size(); ++i)
			w[q[i][1]]=1;
		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);
	}
	bv=vector<int>(m);
	bc=ask(bv);
	int lb=0, rb=m-1;
	while(lb<rb) {
		int mb=(lb+rb)/2;
		vector<int> w=bv;
		fill(w.begin(), w.begin()+mb+1, 1);
		if(ask(w)>bc)
			rb=mb;
		else
			lb=mb+1;
	}
	//cout << lb << endl;
	fill(bv.begin(), bv.begin()+lb, 1);
	bfs(u[lb], d1, p1);
	bfs(v[lb], d2, p2);
	answer(solve(d1, d2, p1), solve(d2, d1, p2));
}

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) {
                ~~^~~~~~~~~
highway.cpp: In function 'int solve(int*, int*, std::vector<std::array<int, 2> >)':
highway.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=mb; i<q.size(); ++i)
                 ~^~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3144 KB Output is correct
2 Correct 36 ms 4176 KB Output is correct
3 Correct 218 ms 12852 KB Output is correct
4 Correct 177 ms 12160 KB Output is correct
5 Correct 236 ms 12168 KB Output is correct
6 Correct 218 ms 12160 KB Output is correct
7 Correct 199 ms 12152 KB Output is correct
8 Correct 209 ms 12168 KB Output is correct
9 Correct 219 ms 12820 KB Output is correct
10 Correct 199 ms 12092 KB Output is correct
11 Correct 232 ms 12184 KB Output is correct
12 Correct 227 ms 12740 KB Output is correct
13 Correct 226 ms 12056 KB Output is correct
14 Correct 239 ms 12720 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4116 KB Output is correct
2 Correct 41 ms 5072 KB Output is correct
3 Correct 65 ms 6140 KB Output is correct
4 Correct 185 ms 12052 KB Output is correct
5 Correct 175 ms 12068 KB Output is correct
6 Correct 177 ms 12060 KB Output is correct
7 Correct 172 ms 12692 KB Output is correct
8 Correct 164 ms 12088 KB Output is correct
9 Correct 164 ms 12764 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3144 KB Output is correct
2 Correct 34 ms 4176 KB Output is correct
3 Correct 153 ms 10516 KB Output is correct
4 Correct 218 ms 12160 KB Output is correct
5 Correct 208 ms 12816 KB Output is correct
6 Correct 210 ms 12152 KB Output is correct
7 Correct 213 ms 12812 KB Output is correct
8 Correct 203 ms 12800 KB Output is correct
9 Correct 231 ms 12812 KB Output is correct
10 Correct 226 ms 12876 KB Output is correct
11 Correct 244 ms 12732 KB Output is correct
12 Correct 224 ms 12048 KB Output is correct
13 Correct 246 ms 12736 KB Output is correct
14 Correct 236 ms 12256 KB Output is correct
15 Correct 215 ms 12128 KB Output is correct
16 Correct 187 ms 12168 KB Output is correct
17 Correct 222 ms 12720 KB Output is correct
18 Correct 251 ms 12772 KB Output is correct
19 Correct 209 ms 12928 KB Output is correct
20 Correct 198 ms 12064 KB Output is correct
21 Correct 188 ms 12372 KB Output is correct
22 Correct 186 ms 13052 KB Output is correct
23 Correct 207 ms 12488 KB Output is correct
24 Correct 199 ms 12468 KB Output is correct
25 Correct 234 ms 12832 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4136 KB Output is correct
2 Correct 29 ms 4344 KB Output is correct
3 Correct 244 ms 12416 KB Output is correct
4 Correct 275 ms 12960 KB Output is correct
5 Correct 299 ms 13448 KB Output is correct
6 Correct 316 ms 13384 KB Output is correct
7 Correct 300 ms 13552 KB Output is correct
8 Correct 294 ms 13664 KB Output is correct
9 Correct 242 ms 10148 KB Output is correct
10 Correct 239 ms 10488 KB Output is correct
11 Correct 259 ms 10824 KB Output is correct
12 Correct 282 ms 12636 KB Output is correct
13 Correct 303 ms 13224 KB Output is correct
14 Correct 328 ms 13504 KB Output is correct
15 Correct 287 ms 13532 KB Output is correct
16 Correct 273 ms 11052 KB Output is correct
17 Correct 180 ms 13160 KB Output is correct
18 Correct 194 ms 12508 KB Output is correct
19 Correct 204 ms 13240 KB Output is correct
20 Correct 217 ms 12620 KB Output is correct
21 Incorrect 291 ms 13416 KB Output is incorrect: {s, t} is wrong.

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4216 KB Output is correct
2 Correct 25 ms 4292 KB Output is correct
3 Correct 258 ms 12584 KB Output is correct
4 Correct 259 ms 12668 KB Output is correct
5 Correct 271 ms 12700 KB Output is correct
6 Correct 299 ms 13440 KB Output is correct
7 Correct 237 ms 12448 KB Output is correct
8 Correct 227 ms 12544 KB Output is correct
9 Correct 261 ms 12836 KB Output is correct
10 Correct 325 ms 13604 KB Output is correct
11 Correct 300 ms 13436 KB Output is correct
12 Correct 285 ms 13456 KB Output is correct
13 Correct 238 ms 10556 KB Output is correct
14 Correct 253 ms 10584 KB Output is correct
15 Correct 243 ms 10516 KB Output is correct
16 Correct 217 ms 10640 KB Output is correct
17 Correct 252 ms 10484 KB Output is correct
18 Correct 255 ms 10396 KB Output is correct
19 Correct 298 ms 12608 KB Output is correct
20 Correct 324 ms 13024 KB Output is correct
21 Correct 282 ms 13492 KB Output is correct
22 Correct 300 ms 13476 KB Output is correct
23 Correct 291 ms 13332 KB Output is correct
24 Correct 307 ms 13556 KB Output is correct
25 Correct 302 ms 13464 KB Output is correct
26 Correct 300 ms 13468 KB Output is correct
27 Correct 171 ms 13224 KB Output is correct
28 Correct 207 ms 12524 KB Output is correct
29 Correct 198 ms 13324 KB Output is correct
30 Correct 191 ms 13224 KB Output is correct
31 Correct 220 ms 13208 KB Output is correct
32 Correct 210 ms 13196 KB Output is correct
33 Correct 206 ms 12660 KB Output is correct
34 Correct 183 ms 13208 KB Output is correct
35 Correct 203 ms 13220 KB Output is correct
36 Correct 203 ms 12460 KB Output is correct
37 Correct 213 ms 13496 KB Output is correct
38 Correct 189 ms 12640 KB Output is correct
39 Correct 307 ms 13572 KB Output is correct
40 Incorrect 300 ms 14088 KB Output is incorrect: {s, t} is wrong.
41 Halted 0 ms 0 KB -