oj.uz

답안 #140364

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
140364 2019-08-02T16:06:33 Z ckodser 통행료 (IOI18_highway) C++14
0 / 100
 1500 ms 28984 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);
	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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 2732 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 36 ms 4356 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2808 KB Output is correct
2 Runtime error 28 ms 4344 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 4556 KB Output is correct
2 Correct 58 ms 4728 KB Output is correct
3 Correct 648 ms 22404 KB Output is correct
4 Correct 762 ms 24512 KB Output is correct
5 Correct 905 ms 27416 KB Output is correct
6 Correct 934 ms 27456 KB Output is correct
7 Correct 971 ms 27444 KB Output is correct
8 Correct 991 ms 27384 KB Output is correct
9 Correct 540 ms 23544 KB Output is correct
10 Correct 414 ms 23756 KB Output is correct
11 Correct 466 ms 25032 KB Output is correct
12 Correct 888 ms 26940 KB Output is correct
13 Correct 848 ms 27144 KB Output is correct
14 Correct 888 ms 27252 KB Output is correct
15 Correct 844 ms 27300 KB Output is correct
16 Correct 682 ms 25136 KB Output is correct
17 Correct 366 ms 21548 KB Output is correct
18 Correct 1078 ms 26596 KB Output is correct
19 Correct 1322 ms 28076 KB Output is correct
20 Correct 1407 ms 28984 KB Output is correct
21 Execution timed out 3012 ms 26816 KB Time limit exceeded

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 30 ms 4444 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -