Submission #140431

#	Time	Username	Problem	Language	Result	Execution time	Memory
140431		arthurconmy	Highway Tolls (IOI18_highway)	C++14	5 / 100	38 ms	780 KiB

highway

#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
	#include "highway.h"
#endif

using namespace std;

using ll = long long;

const int MAXN = 100;
int parent[MAXN];
int par_edge[100];
vector<pair<int,int>> adj[100];

void dfs(int v)
{
	for(auto u:adj[v])
	{
		if(parent[u.first]!=-1) continue;

		parent[u.first]=v;
		par_edge[u.first]=u.second;
		dfs(u.first);
	}
}

void find_pair(int n, vector<int> U, vector<int> V, int A, int B)
{
	for(int i=0; i<n; i++) parent[i]=-1;

	for(int i=0; i<n-1; i++)
	{
		adj[U[i]].push_back({V[i],i});
		adj[V[i]].push_back({U[i],i});
	}

	dfs(0);

	vector<int> askin(n-1);

	ll base = ask(askin);

	vector<ll> anss(n);
	ll max_cur=0;

	for(int i=1; i<n; i++)
	{
		for(int j=0; j<n-1; j++) askin[j]=0;

		int i_copy = i;

		while(i_copy != 0)
		{
			askin[par_edge[i_copy]]=1;
			i_copy=parent[i_copy];
		}

		ll cur = ask(askin);

		anss[i]=cur;
		max_cur=max(max_cur,cur);
	}

	for(int i=0; i<n; i++)
	{
		if(anss[i]==max_cur && anss[parent[i]]!=max_cur) answer(0,i);
	}
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:41:5: warning: unused variable 'base' [-Wunused-variable]
  ll base = ask(askin);
     ^~~~

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