Submission #293934

#	Time	Username	Problem	Language	Result	Execution time	Memory
293934		Dovran	Highway Tolls (IOI18_highway)	C++11	0 / 100	33 ms	16016 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
#define N 200009
#define pii pair <int, int>
#define ff first
#define ss second
#define sz size
#define pb push_back
#define ll long long

using namespace std;

int n, m, ln;
vector<int>e[N];
vector<int>asd;
map<int, int>c[N];
int ansS, ansT;

void find_pair(int NN, std::vector<int>u, std::vector<int>v, int a, int b){
	n=NN;
	m=u.size();
	for(int i=0; i<m; i++){
		e[u[i]].pb(v[i]);
		e[v[i]].pb(u[i]);
		
		c[v[i]][u[i]]=i;
		c[u[i]][v[i]]=i;
		
		
		asd.pb(0);
	}
	ln=ask(asd);
	int l=0, r=m-1;
	int x;
	while(r>=l){
		int md=(l+r)/2;
		for(int i=0; i<=md; i++)
			asd[i]=1;
		x=ask(asd);
		if(x==ln)
			l=md;
		else r=md;
		asd.clear();
		asd.resize(m);
		if(l==r)
			break;
	}
	queue<int> q;
	queue<int> q2;
	q.push(u[l]);
	q2.push(v[l]);
	int vis[N];
	vis[u[l]]=1, vis[v[l]]=1;
	
	vector<pii> p, p2;
	int lft=0, rgt=0;
	while(!q.empty() and !q2.empty()){
		if(!lft){
			int nd=q.front();
				q.pop();
				for(auto i:e[nd])
					if(!vis[i])
						vis[i]=vis[nd]+1, p.pb({vis[i], i});
			sort(p.begin(), p.end());
			for(auto i:p)
				for(auto j:e[i.ss]) asd[c[i.ss][j]]=1;
			x=ask(asd);
			if(ask(asd)!=ln){
				l=0, r=p.sz()-1;
				while(l>=r){
					int md=(l+r)/2;
					for(int i=0; i<=md; i++)
						for(auto j:e[p[i].ss]) asd[c[p[i].ss][j]]=1;
					x=ask(asd);
					if(x!=ln)
						r=md;
					else l=md;
					
					asd.clear(), asd.resize(m);
					if(l==r)
						break;
				}
				ansS=p[l].ss;
				lft=1;
			}
			asd.clear(), asd.resize(m);
		}
		if(!rgt){
			int nd2=q2.front();
			q2.pop();
			for(auto i:e[nd2])
				if(!vis[i])
					vis[i]=vis[nd2]+1, p2.pb({vis[i], i});
			sort(p2.begin(), p2.end());

			for(auto i:p2)
				for(auto j:e[i.ss]) asd[c[i.ss][j]]=1;
			x=ask(asd);
			if(ask(asd)!=ln){
				l=0, r=p2.sz()-1;
				while(l>=r){
					int md=(l+r)/2;
					for(int i=0; i<=md; i++)
						for(auto j:e[p2[i].ss]) asd[c[p2[i].ss][j]]=1;
					x=ask(asd);
					if(x!=ln)
						r=md;
					else l=md;
					
					asd.clear(), asd.resize(m);
					if(l==r)
						break;
				}
				ansT=p2[l].ss;
				rgt=1;
			}
			asd.clear(), asd.resize(m);
		}
	}
	answer(ansS, ansT);
}

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