oj.uz

Submission #140368

# Submission time Handle Problem Language Result Execution time Memory
140368 2019-08-02T16:17:31 Z ckodser Highway Tolls (IOI18_highway) C++14
18 / 100
 855 ms 33120 KB 
#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;

vector<ll> ver[maxn*2];
bool check(ll s,ll t,vector<ll> &U,vector<ll> &V,ll n){
	for(auto r:tr){
		for(ll i=0;i<2*n;i++)ver[i].clear();
		fill(mn,mn+n,inf);
		
		ver[0].pb(s);
		mn[s]=0;
		for(ll w=0;w<2*n;w++){
			for(auto v:ver[w]){
				if(mn[v]==w){
					for(auto e:ger[v]){
						ll u=(V[e]^U[e]^v);
						if(mn[u]>w+r[e]+1){
							mn[u]=w+r[e]+1;
							ver[mn[u]].pb(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);
	for(auto e:vec){
		fill(daste,daste+n,0);
		daste[e.S]=1;
		if(findGir(v,u)){
			answer(e.F,e.S);
			return;
		}
	}
	return ;

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7412 KB Output is correct
2 Runtime error 8 ms 7416 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 7548 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 9072 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7544 KB Output is correct
2 Runtime error 49 ms 9160 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 9432 KB Output is correct
2 Correct 56 ms 9544 KB Output is correct
3 Correct 726 ms 28092 KB Output is correct
4 Correct 816 ms 30124 KB Output is correct
5 Correct 792 ms 32684 KB Output is correct
6 Correct 855 ms 32808 KB Output is correct
7 Correct 829 ms 32776 KB Output is correct
8 Correct 826 ms 32820 KB Output is correct
9 Correct 480 ms 27988 KB Output is correct
10 Correct 382 ms 28336 KB Output is correct
11 Correct 429 ms 29744 KB Output is correct
12 Correct 701 ms 32252 KB Output is correct
13 Correct 771 ms 32740 KB Output is correct
14 Correct 787 ms 32620 KB Output is correct
15 Correct 790 ms 32788 KB Output is correct
16 Correct 544 ms 29864 KB Output is correct
17 Correct 420 ms 27616 KB Output is correct
18 Correct 464 ms 27928 KB Output is correct
19 Correct 447 ms 28052 KB Output is correct
20 Correct 460 ms 27804 KB Output is correct
21 Correct 728 ms 33120 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 9144 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -