oj.uz

Submission #75185

# Submission time Handle Problem Language Result Execution time Memory
75185 2018-09-08T16:13:20 Z tmwilliamlin168 Highway Tolls (IOI18_highway) C++14
51 / 100
 290 ms 8888 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=9e4;
int n, qu[mxN], qt, p[mxN];
vector<int> eu, ev, adj[mxN], w;
ll ba;

int bfs(int s) {
	qt=0;
	qu[qt++]=s;
	memset(p, -1, 4*n);
	p[s]=-2;
	for(int i=0; i<n; ++i) {
		int u=qu[i];
		for(int e : adj[u]) {
			int v=u^eu[e]^ev[e];
			if(p[v]==-1) {
				p[v]=e;
				qu[qt++]=v;
			}
		}
	}
	int lb=1, rb=n-1;
	while(lb<=rb) {
		int mb=(lb+rb)/2;
		fill(w.begin(), w.end(), 0);
		for(int i=mb; i<n; ++i)
			w[p[qu[i]]]=1;
		if(ask(w)>ba)
			lb=mb+1;
		else
			rb=mb-1;
	}
	return qu[rb];
}

void find_pair(int n2, vector<int> u, vector<int> v, int a, int b) {
	n=n2, eu=u, ev=v;
	if(u.size()!=n-1) {
		answer(1, 3);
		return;
	}
	w.resize(n-1);
	ba=ask(w);
	for(int i=0; i<n-1; ++i) {
		adj[u[i]].push_back(i);
		adj[v[i]].push_back(i);
	}
	int s=bfs(0), t=bfs(s);
	answer(s, t);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:43:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(u.size()!=n-1) {
     ~~~~~~~~^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2444 KB Output is correct
2 Correct 4 ms 2428 KB Output is correct
3 Correct 4 ms 2344 KB Output is correct
4 Correct 4 ms 2344 KB Output is correct
5 Correct 4 ms 2428 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2448 KB Output is correct
8 Correct 4 ms 2448 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 2428 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2552 KB Output is correct
2 Correct 27 ms 3064 KB Output is correct
3 Correct 230 ms 8584 KB Output is correct
4 Correct 233 ms 8548 KB Output is correct
5 Correct 253 ms 8548 KB Output is correct
6 Correct 203 ms 8540 KB Output is correct
7 Correct 241 ms 8604 KB Output is correct
8 Correct 260 ms 8540 KB Output is correct
9 Correct 245 ms 8628 KB Output is correct
10 Correct 235 ms 8536 KB Output is correct
11 Correct 263 ms 8452 KB Output is correct
12 Correct 290 ms 8452 KB Output is correct
13 Correct 266 ms 8456 KB Output is correct
14 Correct 279 ms 8500 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2984 KB Output is correct
2 Correct 41 ms 3744 KB Output is correct
3 Correct 58 ms 4432 KB Output is correct
4 Correct 182 ms 8444 KB Output is correct
5 Correct 163 ms 8448 KB Output is correct
6 Correct 150 ms 8528 KB Output is correct
7 Correct 184 ms 8552 KB Output is correct
8 Correct 141 ms 8480 KB Output is correct
9 Correct 172 ms 8448 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2472 KB Output is correct
2 Correct 27 ms 3116 KB Output is correct
3 Correct 190 ms 7208 KB Output is correct
4 Correct 252 ms 8560 KB Output is correct
5 Correct 227 ms 8604 KB Output is correct
6 Correct 216 ms 8576 KB Output is correct
7 Correct 238 ms 8588 KB Output is correct
8 Correct 268 ms 8540 KB Output is correct
9 Correct 243 ms 8540 KB Output is correct
10 Correct 267 ms 8624 KB Output is correct
11 Correct 239 ms 8432 KB Output is correct
12 Correct 233 ms 8536 KB Output is correct
13 Correct 245 ms 8544 KB Output is correct
14 Correct 256 ms 8428 KB Output is correct
15 Correct 286 ms 8656 KB Output is correct
16 Correct 249 ms 8544 KB Output is correct
17 Correct 262 ms 8452 KB Output is correct
18 Correct 265 ms 8656 KB Output is correct
19 Correct 261 ms 8564 KB Output is correct
20 Correct 265 ms 8436 KB Output is correct
21 Correct 204 ms 8792 KB Output is correct
22 Correct 200 ms 8888 KB Output is correct
23 Correct 228 ms 8792 KB Output is correct
24 Correct 202 ms 8768 KB Output is correct
25 Correct 246 ms 8580 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 2680 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 2680 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -