oj.uz

Submission #140362

# Submission time Handle Problem Language Result Execution time Memory
140362 2019-08-02T16:04:05 Z ckodser Highway Tolls (IOI18_highway) C++14
0 / 100
 922 ms 27256 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;

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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Runtime error 4 ms 2680 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 5 ms 2808 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 21 ms 4344 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 6 ms 2808 KB Output is correct
2 Runtime error 23 ms 4432 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4492 KB Output is correct
2 Correct 50 ms 4676 KB Output is correct
3 Correct 680 ms 22280 KB Output is correct
4 Correct 767 ms 23924 KB Output is correct
5 Correct 922 ms 27124 KB Output is correct
6 Correct 907 ms 27224 KB Output is correct
7 Correct 876 ms 27220 KB Output is correct
8 Correct 919 ms 27256 KB Output is correct
9 Incorrect 555 ms 23532 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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