Submission #263174

#	Time	Username	Problem	Language	Result	Execution time	Memory
263174		SuhaibSawalha1	Highway Tolls (IOI18_highway)	C++14	0 / 100	299 ms	262148 KiB

highway

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

set <int> candidate;
int c1 , c2;
const int N = 2e5;
vector <pair<int,int>> adj[N];
vector <int> to_ask;
long long ans;

void dfs (int u = 0 , int p = -1 , long long cur = 0){
	if (cur == ans)
		candidate.insert(u);
	if (cur != ans && candidate.count(u))
		candidate.erase(u);
	for (auto v : adj[u])
		if (v.first ^ p)
			dfs(v.first,u,cur + (to_ask[v.second] ? c1 : c2));
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	int M = U.size();
	c1 = A;
	c2 = B;
	for (int i = 0 ; i < M ; ++i){
		adj[U[i]].push_back({V[i],i});
		adj[V[i]].push_back({U[i],i});
	}
 	for (int i = 0 ; i < M ; ++i){
  		to_ask = vector <int> (M,0);
  		to_ask[i] = 1;
  		ans = ask(to_ask);
  		dfs();
	}

  	answer(0,*candidate.begin());
}

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