Submission #297455

#	Time	Username	Problem	Language	Result	Execution time	Memory
297455		rqi	통행료 (IOI18_highway)	C++14	18 / 100	132 ms	8728 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<pi> vpi;

#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()

const int mx = 90005;
int N, M;
ll A, B;
int D;
vi U, V;
vpi adj[mx]; //node, edge

int getDist(){
	vi w(M, 0);
	return ask(w)/A;
}

vpi jeds; //edges just before degree d nodes, label of nodes

void findJeds(int node, int d = 0, int prv = -1){
	for(auto u: adj[node]){
		if(u.f == prv) continue;
		if(d+1 == D){
			jeds.pb(mp(u.s, u.f));
			continue;
		}
		findJeds(u.f, d+1, node);
	}
}

void find_pair(int _N, vi _U, vi _V, int _A, int _B) {
	N = _N;
	U = _U;
	V = _V;
	M = sz(U);
	for(int i = 0; i < M; i++){
		adj[U[i]].pb(mp(V[i], i));
		adj[V[i]].pb(mp(U[i], i));
	}
	A = _A;
	B = _B;


	if(M == N-1){ //TREE CASE
		bool isLine = 1;
		for(int i = 0; i < M; i++){
			if(U[i] != i || V[i] != i+1) isLine = 0;
		}
		if(isLine){
			D = getDist();
			vi sts;
			for(int i = 0; i < N; i++){
				if(i+D < N) sts.pb(i);
			}

			while(sz(sts) > 1){
				vi nsts;
				vi osts;
				for(int i = 0; i < sz(sts)/2; i++){
					nsts.pb(sts[i]);
				}
				for(int i = sz(sts)/2; i < sz(sts); i++){
					osts.pb(sts[i]);
				}
				vi w(M, 0);
				for(auto u: nsts) w[u] = 1;
				if(ask(w) == A*D){
					sts = osts;
				}
				else sts = nsts;
			}
			answer(sts[0], sts[0]+D);
			return;
		}
		D = getDist();
		findJeds(0, 0);
		while(sz(jeds) > 1){
			vpi njeds;
			vpi ojeds;
			for(int i = 0; i < sz(jeds)/2; i++){
				njeds.pb(jeds[i]);
			}
			for(int i = sz(jeds)/2; i < sz(jeds); i++){
				ojeds.pb(jeds[i]);
			}
			vi w(M, 0);
			for(auto u: njeds){
				w[u.f] = 1;
			}
			if(ask(w) == A*D){
				jeds = ojeds;
			}
			else jeds = njeds;
		}
		answer(0, jeds[0].s);
		return;
	}
	

}

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