Submission #596949

#	Time	Username	Problem	Language	Result	Execution time	Memory
596949		FatihSolak	Highway Tolls (IOI18_highway)	C++17	6 / 100	208 ms	262144 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
vector<pair<int,int>> adj[N];
int par[N];
int paredge[N];
int dep[N];
vector<int> w;
void dfs(int v,int pr,int edge){
	//cout << v << " " << pr << " " << edge << endl;
	par[v] = pr;
	paredge[v] = edge;
	for(auto u:adj[v]){
		if(u.first == pr)continue;
		dep[u.first] = dep[v] + 1;
		dfs(u.first,v,u.second);
	}
}
void dfs2(int v,int pr){
	w[paredge[v]] = 1;
	for(auto u:adj[v]){
		if(u.first == pr)continue;
		dfs2(u.first,v);
	}
}
vector<int> xx;
void dfs3(int v,int pr,int target){
	if(dep[v] == target)
		xx.push_back(v);
	for(auto u:adj[v]){
		if(u.first == pr)continue;
		dfs3(u.first,v,target);
	}
}
int group[N];
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
	int m = u.size();
	for(int i = 0;i<m;i++){
		adj[u[i]].push_back({v[i],i});
		adj[v[i]].push_back({u[i],i});
	}
	w.assign(m,0);
	if(a == 1 && b == 2){
		//solution with making sure s on first group t on second group
		mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
		vector<int> x;
		for(int i = 0;i<n;i++){
			x.push_back(i);
		}
		while(1){
			shuffle(x.begin(),x.end(),rng);
			int mid = (n-1) / 2;
			w.assign(m,0);
			for(int i = 0;i<=mid;i++){
				group[x[i]] = 0;
			}
			for(int i = mid+1;i<n;i++){
				group[x[i]] = 1;
			}
			for(int i = 0;i<m;i++){
				if(group[u[i]] == group[v[i]]){
					w[i] = 1;
				}
			}
			if(ask(w) & 1){
				break;
			}
		}
		int s  = -1,t = -1;
		int ll = 0,rr = (n-1)/2;
		while(ll < rr){
			int mid = (ll + rr)/2;
			w.assign(m,0);
			for(int i = 0;i<=mid;i++){
				group[x[i]] = 0;
			}
			for(int i = mid+1;i<n;i++){
				group[x[i]] = 1;
			}
			for(int i = 0;i<m;i++){
				if(group[u[i]] == group[v[i]]){
					w[i] = 1;
				}
			}
			if(ask(w) & 1){
				rr = mid;
			}
			else ll = mid+1;
		}
		s = x[ll];
		ll = (n-1)/2 + 1,rr = n-1;
		while(ll < rr){
			int mid = (ll + rr+1)/2;
			w.assign(m,0);
			for(int i = 0;i<=mid;i++){
				group[x[i]] = 0;
			}
			for(int i = mid+1;i<n;i++){
				group[x[i]] = 1;
			}
			for(int i = 0;i<m;i++){
				if(group[u[i]] == group[v[i]]){
					w[i] = 1;
				}
			}
			if(ask(w) & 1){
				ll = mid;
			}
			else rr = mid-1;
		}
		t = x[ll];
		answer(s,t);
		//solution with finding xor of s and t
		/*
		int s = 0;
		int xr = 0;
		int least = -1;
		for(int i = 0;(1<<i)<n;i++){
			w.assign(m,0);
			for(int j = 0;j<m;j++){
				int nowmask = (1<<i);
				if( ((u[j] & nowmask) == nowmask)  == ((v[j] & nowmask) == nowmask)){
					w[j] = 1;
				}
			}
			if(ask(w) & 1){
				if(least == -1){
					least = i;
					s = (1<<least);
				}
				xr += (1<<i);
			}
		}
		assert(least != -1);
		for(int i = 0;(1<<i)<n;i++){
			if(i == least)continue;
			w.assign(m,0);
			for(int j = 0;j<m;j++){
				int nowmask = (1<<i) + (1<<least);
				if( ((u[j] & nowmask) == nowmask)  == ((v[j] & nowmask) == nowmask)){
					w[j] = 1;
				}
			}
			if(ask(w) & 1){
				s += (1<<i);
			}
		}
		answer(s,xr^s);*/
		return;
	}
	long long len = ask(w) / a;
	vector<int> x;
	for(int i = 0;i<m;i++){
		x.push_back(i);
	}
	while(x.size() > 1){
		vector<int> tmp;
		while(tmp.size() < x.size()){
			tmp.push_back(x.back());
			x.pop_back();
		}
		w.assign(m,0);
		for(auto u:tmp){
			w[u] = 1;
		}
		if(ask(w) != len * a){
			x = tmp;
		}
	}
	int root = u[x[0]];
	//cout << root << endl;
	dfs(root,-1,-1);
	w.assign(m,0);
	dfs2(v[x[0]],root);
	int dep1 = (ask(w) - len*a) / (b-a);
	int dep2 = len - dep1;
	int s = -1,t = -1;
	if(dep1 == 0)s = root;
	if(dep2 == 0)t = root;
	//cout << dep1 << " " << dep2 << endl;
	if(s == -1){
		xx.clear();
		dfs3(v[x[0]],root,dep1);
		while(xx.size() > 1){
			vector<int> tmp;
			while(tmp.size() < xx.size()){
				tmp.push_back(xx.back());
				xx.pop_back();
			}
			w.assign(m,0);
			for(auto u:tmp){
				w[paredge[u]] = 1;
			}
			if(ask(w) != len * a){
				xx = tmp;
			}
		}
		s = xx[0];
	}
	if(t == -1){
		xx.clear();
		for(auto u:adj[root]){
			if(u.first == v[x[0]])continue;
			dfs3(u.first,root,dep2);
		}
		while(xx.size() > 1){
			vector<int> tmp;
			while(tmp.size() < xx.size()){
				tmp.push_back(xx.back());
				xx.pop_back();
			}
			w.assign(m,0);
			for(auto u:tmp){
				w[paredge[u]] = 1;
			}
			if(ask(w) != len * a){
				xx = tmp;
			}
		}
		t = xx[0];
	}
	answer(s,t);
}

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