Submission #297430

#	Time	Username	Problem	Language	Result	Execution time	Memory
297430		rqi	통행료 (IOI18_highway)	C++14	12 / 100	148 ms	8696 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
		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: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31