Submission #123859

#	Time	Username	Problem	Language	Result	Execution time	Memory
123859		nvmdava	Highway Tolls (IOI18_highway)	C++17	5 / 100	227 ms	9148 KiB

highway

#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 (stderr)

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 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31