oj.uz

Submission #123859

# Submission time Handle Problem Language Result Execution time Memory
123859 2019-07-02T08:10:01 Z nvmdava Highway Tolls (IOI18_highway) C++17
5 / 100
 227 ms 9148 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) >> 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 2760 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2760 KB Output is correct
5 Correct 4 ms 2676 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2552 KB Output is correct
8 Correct 4 ms 2676 KB Output is correct
9 Correct 4 ms 2760 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 4 ms 2672 KB Output is correct
12 Correct 4 ms 2672 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2728 KB Output is correct
2 Correct 23 ms 3320 KB Output is correct
3 Incorrect 199 ms 8688 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3368 KB Output is correct
2 Incorrect 45 ms 4148 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 2680 KB Output is correct
2 Correct 24 ms 3368 KB Output is correct
3 Correct 145 ms 7412 KB Output is correct
4 Correct 183 ms 8688 KB Output is correct
5 Correct 193 ms 8684 KB Output is correct
6 Correct 184 ms 8616 KB Output is correct
7 Correct 182 ms 8640 KB Output is correct
8 Correct 191 ms 8548 KB Output is correct
9 Incorrect 189 ms 8624 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3436 KB Output is correct
2 Correct 30 ms 3464 KB Output is correct
3 Incorrect 191 ms 8916 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3384 KB Output is correct
2 Correct 31 ms 3448 KB Output is correct
3 Correct 227 ms 8956 KB Output is correct
4 Incorrect 212 ms 9148 KB Output isn't correct
5 Halted 0 ms 0 KB -