oj.uz

Submission #123863

# Submission time Handle Problem Language Result Execution time Memory
123863 2019-07-02T08:12:55 Z nvmdava Highway Tolls (IOI18_highway) C++17
5 / 100
 291 ms 9900 KB 
#include "highway.h"
#define ff first
#define ss second
#define pii pair<int, int>
#include <bits/stdc++.h>
using namespace std;

long long def;
vector<int> path;
int in[100000];
vector<int> p;
vector<int> adj[100000];
bool ina[130005];
vector<int> w;

int find(int v, int p){
	vector<int> ls;
	for(int x : adj[v]){
		if(ina[x] == 0 || path[x] == v + p) continue;
		ls.push_back(x);
	}
	if(ls.empty()) return v;
	
	int l = -1, r = ls.size();
	while(l + 1 != r){
		int m = (l + r) >> 1;
		for(int i = 0; i <= m; i++)
			w[ls[i]] = 1;
		if(ask(w) > def) r = m;
		else l = m;
		for(int i = 0; i <= m; i++)
			w[ls[i]] = 0;
	}
	
	if(r == ls.size()) return v;
	int u = path[ls[r]] - v;
	ls.clear();
	return find(u, v);
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	int m = V.size();
	for(int i = 0; i < m; i++){
		path.push_back(U[i] + V[i]);
		adj[U[i]].push_back(i);
		adj[V[i]].push_back(i);
	}
		
	int l = 0, r = m - 1;
	def = ask(vector<int>(m, 0));
	while(l != r){
		int mm = (l + r) >> 1;
		vector<int> w = vector<int>(m ,0);
		for(int i = 0; i <= mm; i++)
			w[i] = 1;
		if(ask(w) > def) r = mm;
		else l = mm + 1;
	}
	
	queue<int> q;
	q.push(V[l]);
	q.push(U[l]);
	in[V[l]] = in[U[l]] = 1;
	
	p.push_back(l);
	
	while(!q.empty()){
		int v = q.front();
		q.pop();
		for(int x : adj[v]){
			if(in[path[x] - v])continue;
			in[path[x] - v] = 1;
			q.push(path[x] - v);
			p.push_back(x);
			ina[x] = 1;
		}
	}
	w = vector<int>(m, 1);
	for(int x : p)
		w[x] = 0;
	
	answer(find(V[l], U[l]), find(U[l], V[l]));
}

Compilation message

highway.cpp: In function 'int find(int, int)':
highway.cpp:35:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(r == ls.size()) return v;
     ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 22 ms 3412 KB Output is correct
3 Incorrect 216 ms 8684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3368 KB Output is correct
2 Incorrect 52 ms 4228 KB Output is incorrect: more than 100 calls to ask.
3 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2812 KB Output is correct
2 Correct 18 ms 3364 KB Output is correct
3 Correct 121 ms 7408 KB Output is correct
4 Correct 152 ms 8628 KB Output is correct
5 Correct 184 ms 8576 KB Output is correct
6 Correct 169 ms 8680 KB Output is correct
7 Correct 180 ms 8744 KB Output is correct
8 Correct 179 ms 8608 KB Output is correct
9 Incorrect 199 ms 8680 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3428 KB Output is correct
2 Correct 25 ms 3500 KB Output is correct
3 Incorrect 240 ms 9028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3428 KB Output is correct
2 Correct 30 ms 3432 KB Output is correct
3 Correct 214 ms 9020 KB Output is correct
4 Partially correct 236 ms 9176 KB Output is partially correct
5 Partially correct 222 ms 9176 KB Output is partially correct
6 Correct 288 ms 9900 KB Output is correct
7 Correct 226 ms 8944 KB Output is correct
8 Correct 226 ms 9064 KB Output is correct
9 Correct 249 ms 9160 KB Output is correct
10 Correct 281 ms 9844 KB Output is correct
11 Correct 235 ms 9804 KB Output is correct
12 Correct 258 ms 9860 KB Output is correct
13 Correct 244 ms 8736 KB Output is correct
14 Correct 238 ms 8440 KB Output is correct
15 Correct 221 ms 8728 KB Output is correct
16 Correct 244 ms 8448 KB Output is correct
17 Correct 246 ms 8956 KB Output is correct
18 Correct 250 ms 8440 KB Output is correct
19 Correct 274 ms 9284 KB Output is correct
20 Correct 282 ms 9456 KB Output is correct
21 Correct 259 ms 9716 KB Output is correct
22 Correct 253 ms 9628 KB Output is correct
23 Correct 285 ms 9692 KB Output is correct
24 Correct 291 ms 9640 KB Output is correct
25 Correct 270 ms 9644 KB Output is correct
26 Correct 267 ms 9656 KB Output is correct
27 Incorrect 192 ms 9376 KB Output is incorrect: more than 100 calls to ask.
28 Halted 0 ms 0 KB -