Submission #1241784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241784		YassirSalama	Highway Tolls (IOI18_highway)	C++20	12 / 100	467 ms	327680 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
const int maxn = 1e5+100;
vector<pair<int,int>> v[maxn];
vector<int> w;
int a,b;
int x;
set<int> s;
int depth[maxn];
void dfs(int node,int par){
	if(depth[node]!=x){
		if(s.find(node)!=s.end())
			s.erase(node);
	}
	for(auto x : v[node]){
		if(x.F==par) continue;
		if(w[x.S]==0){
			depth[x.F] = depth[node]+a;
		}else depth[x.F] = depth[node]+b;
		dfs(x.F,node);
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	srand(time(NULL));
	int n = N;
	a = A;
	b = B;
	for(int i = 0;i<n;i++){
		s.insert(i);
	}
	int m = U.size();
	for(int i = 0;i<m;i++){
		int a = U[i];
		int b = V[i];
		v[a].pb({b,i});
		v[b].pb({a,i});
	}
	int t = 60;
	while(t--){
		if(s.size()==1) break;
		w.clear();
		w.resize(m,0);
		for(int i = 0;i<n;i++){
			depth[i] = 0;
		}
		for(int j = 0;j<m;j++){
			w[j] = rand()%2;
		}
		x = ask(w);
		dfs(0,0);
	}
	int ans = *s.begin();
	answer(0,ans);
}

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