Submission #140361

#	Time	Username	Problem	Language	Result	Execution time	Memory
140361		ckodser	Highway Tolls (IOI18_highway)	C++14	0 / 100	962 ms	27224 KiB

highway

#include "highway.h"
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}

#define ll int
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=1e5+500;
ll logg=17;
const ll inf=1e9+900;

bool daste[maxn];
ll rp[maxn];
vector<ll> ger[maxn];
ll mn[maxn];

vector<vector<ll> > tr;

bool check(ll s,ll t,vector<ll> &U,vector<ll> &V,ll n){
	for(auto r:tr){
		fill(mn,mn+n,inf);
		queue<pii> qu;
		qu.push(mp(0,s));
		while(qu.size()){
			ll v=qu.front().S;
			ll w=qu.front().F;
			qu.pop();
			if(mn[v]>w){
				mn[v]=w;
				for(auto e:ger[v]){
					ll u=(V[e]^U[e]^v);
					if(mn[u]>w+r[e]+1){
						qu.push(mp(w+r[e]+1,u));
					}
				}
			}
		}
		if(mn[t]!=r.back()){
			return 0;
		}
	}
	return 1;
}
bool findGir(vector<ll> &u,vector<ll> &v){
	ll m=u.size();
	vector<ll> w(m);
	for(ll i=0;i<m;i++){
		if(daste[v[i]]==daste[u[i]]){
			w[i]=1;
		}
	}
	ll t=ask(w);
	w.pb(t);
	tr.pb(w);
	return ((t&1));
}

void find_pair(int n,vector<int> u,vector<int> v, int a, int b) {
	if(a!=1 && b!=2){
		return;
	}
	ll m=v.size();
	for(ll i=0;i<m;i++){
		ger[u[i]].pb(i);
		ger[v[i]].pb(i);
	}
	logg=1;
	ll nn=n;
	while(nn>1){
		logg++;
		nn/=2;
	}
	ll x=0;
	for(ll i=0;i<logg;i++){
		for(ll j=0;j<n;j++){
			daste[j]=((j>>i)&1);
		}
		x^=((1<<i)*findGir(u,v));
	}
	vector<ll> p(n);
	for(ll i=0;i<n;i++){
		p[i]=i;
	}
	random_shuffle(p.begin(),p.end());
	ll y=0;
	for(ll i=0;i<logg;i++){
		for(ll j=0;j<n;j++){
			daste[p[j]]=((j>>i)&1);
		}
		y^=((1<<i)*findGir(u,v));
	}
	for(ll i=0;i<n;i++){
		rp[p[i]]=i;
	}
	vector<pii> vec;
	for(ll i=0;i<n;i++){
		ll a1=(i^x);
		ll a2=p[(rp[i]^y)];
		if(a1==a2 && i<a1){
			vec.pb(mp(i,a1));
		}
	}
	vector<pii> ves;
	for(auto e:vec){
		if(check(e.F,e.S,u,v,n)){
			ves.pb(e);
		}
	}
	if(ves.empty())exit(1);
	answer(ves.back().F,ves.back().S);
	return ;

}

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