Submission #443012

#	Time	Username	Problem	Language	Result	Execution time	Memory
443012		vanic	Highway Tolls (IOI18_highway)	C++14	51 / 100	244 ms	16176 KiB

highway

#include "highway.h"
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

typedef long long ll;

const int maxn=1e5, maxm=2e5;

int m, a, b, n;
vector < int > ms[maxn];
vector < int > ms1[maxn];
pair < int, int > edge[maxm];
vector < int > Q;
ll poc;

int nadji(int l, int r){
	if(l==r-1){
		return l;
	}
	int mid=(l+r)/2;
	for(int i=l; i<mid; i++){
		Q[i]=1;
	}
	ll val=ask(Q);
	if(val>poc){
		for(int i=l; i<mid; i++){
			Q[i]=0;
		}
		return nadji(l, mid);
	}
	else{
		return nadji(mid, r);
	}
	
}

int dist[2][maxn];

void bfs(int x, int ind){
	queue < int > q;
	q.push(x);
	dist[ind][x]=0;
	while(!q.empty()){
		x=q.front();
		q.pop();
		for(int i=0; i<(int)ms[x].size(); i++){
			if(dist[ind][ms[x][i]]==-1  && !Q[ms1[x][i]]){
				dist[ind][ms[x][i]]=dist[ind][x]+1;
				q.push(ms[x][i]);
			}
		}
	}
}

int col[maxn];
vector < int > Q1;  

int bio[maxn];
vector < int > red;

void bfs1(int x){
	queue < int > q;
	q.push(x);
	memset(bio, -1, sizeof(bio));
	bio[x]=0;
	while(!q.empty()){
		x=q.front();
		q.pop();
		for(int i=0; i<(int)ms[x].size(); i++){
			if(bio[ms[x][i]]==-1 && col[ms[x][i]]==col[x] && !Q[ms1[x][i]]){
				bio[ms[x][i]]=bio[x]+1;
				red.push_back(ms1[x][i]);
//				cout << x << ' ' << ms[x][i] << ' ' << ms1[x][i] << endl;
				q.push(ms[x][i]);
			}
		}
	}
}



ll maksi;

int rijesi(int l, int r){
	if(l==r-1){
		return l;
	}
	int mid=(l+r)/2;
	for(int i=mid; i<r; i++){
		if(red[i]==-1){
			continue;
		}
		Q[red[i]]=1;
	}
/*	cout << "querijam " << l << ' ' << r << endl;
	for(int i=0; i<Q.size(); i++){
		cout << Q[i] << ' ';
	}
	cout << endl;*/
//	cout << ask(Q) << endl;
	if(ask(Q)==maksi){
//		cout << "ima" << endl;
		return rijesi(l, mid);
	}
	else{
		for(int i=mid; i<r; i++){
			if(red[i]==-1){
				continue;
			}
			Q[red[i]]=0;
		}
		return rijesi(mid, r);
	}
}

void find_pair(int N, vector<int> u, vector<int> v, int A, int B) {
	m = u.size();
	n=N;
	a=A;
	b=B;
	for(int i=0; i<m; i++){
		edge[i]={u[i], v[i]};
		ms[u[i]].push_back(v[i]);
		ms[v[i]].push_back(u[i]);
		ms1[u[i]].push_back(i);
		ms1[v[i]].push_back(i);
	}
	Q.resize(m, 0);
	poc=ask(Q);
	int x=nadji(0, m);

/*	for(int i=0; i<Q.size(); i++){
		cout << Q[i] << ' ';
	}
	cout << endl;*/
	Q1=Q;


	memset(dist[0], -1, sizeof(dist[0]));
	memset(dist[1], -1, sizeof(dist[1]));
	bfs(edge[x].first, 0);
	bfs(edge[x].second, 1);
	for(int i=0; i<n; i++){
		if(dist[0][i]<dist[1][i]){
			col[i]=1;
		}
		else if(dist[0][i]==dist[1][i]){
			col[i]=2;
		}
	}
	red.push_back(-1);
	bfs1(edge[x].first);
	for(int i=0; i<m; i++){
		Q[i]=1;
	}
	for(int i=1; i<(int)red.size(); i++){
		Q[red[i]]=0;
	}
	maksi=ask(Q);
//	cout << "maksi " << maksi << endl;
/*	for(int i=1; i<(int)red.size(); i++){
		Q[red[i]]=1;
	}*/
/*	for(int i=0; i<Q.size(); i++){
		cout << Q[i] << ' ';
	}
	cout << endl;
	cout << "red ";
	for(int i=0; i<(int)red.size(); i++){
		cout << red[i] << ' ';
	}
	cout << endl;*/
	int y=red[rijesi(0, red.size())];
	int sol1, sol2;
//	cout << y << endl;
	if(y==-1){
		sol1=edge[x].first;
	}
	else if(bio[edge[y].first]>bio[edge[y].second]){
		sol1=edge[y].first;
	}
	else{
		sol1=edge[y].second;
	}
/*	for(int i=0; i<n; i++){
		sta[i].clear();
		sta1[i].clear();
	}*/
	red.clear();
	red.push_back(-1);
	Q=Q1;
	bfs1(edge[x].second);
	for(int i=0; i<m; i++){
		Q[i]=1;
	}
	for(int i=1; i<(int)red.size(); i++){
		Q[red[i]]=0;
	}
	maksi=ask(Q);
	
/*	cout << "trazim " << endl;
	for(int i=0; i<Q.size(); i++){
		cout << Q[i] << ' ';
	}
	cout << endl;*/
/*	for(int i=1; i<(int)red.size(); i++){
		Q[red[i]]=1;
	}*/
/*	cout << "red2 ";
	for(int i=0; i<(int)red.size(); i++){
		cout << red[i] << ' ';
	}
	cout << endl;*/
	y=red[rijesi(0, red.size())];
//	cout << "maksi " << maksi << endl;
//	cout << y << endl;
	if(y==-1){
		sol2=edge[x].second;
	}
	else if(bio[edge[y].first]>bio[edge[y].second]){
		sol2=edge[y].first;
	}
	else{
		sol2=edge[y].second;
	}
//	cout << sol1 << ' ' << sol2 << ' ' << x << endl;
	answer(sol1, sol2);
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31