Submission #427411

#	Time	Username	Problem	Language	Result	Execution time	Memory
427411		Monchito	Highway Tolls (IOI18_highway)	C++14	5 / 100	128 ms	7576 KiB

highway

#include "highway.h"
using namespace std;

#define sz(x) (int)x.size()

const int MAXN = 9e4;

int M;
vector<pair<int,int>> G[MAXN];
bool vis[MAXN];

vector<int> p;
long long cost;

void DFS(int u, int& ans) {
	vis[u] = true;

	for(pair<int,int> v : G[u]) {
		if(!vis[v.first]) {
			p[v.second] = 1;
			if(ask(p) > cost) {
				p[v.second] = 0;
				DFS(v.first, ans);			
				return;
			}
		}	
	}

	ans = u;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {	
	M = sz(U);
	p = vector<int>(M, 0);

	cost = ask(p);

	for(int i=0; i<M; i++) {
		G[U[i]].push_back({V[i], i});
		G[V[i]].push_back({U[i], i});
	}

	int ans=-1;

	DFS(0, ans);
	answer(0, ans);
}

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