Submission #139333

#	Time	Username	Problem	Language	Result	Execution time	Memory
139333		Lawliet	Highway Tolls (IOI18_highway)	C++14	5 / 100	40 ms	660 KiB

highway

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

#define MAX 90010

using namespace std;
typedef pair<int,int> pii;
typedef long long int lli;

int N, A, B;

int degree[MAX];

bool inPath[MAX];

pii edges[MAX];

vector<int> question;

/*int ask(vector<int> p)
{
	for(int g = 0 ; g < N - 1 ; g++)
		printf("%d ",p[g]);

	int a;
	scanf("%d",&a);

	return a;
}

void answer(int i, int j)
{
	printf("========= %d %d\n",i,j);
}*/

void find_pair(int n, vector<int> U, vector<int> V, int a, int b)
{
	N = n; A = a; B = b;

	for(int g = 0 ; g < N - 1 ; g++)
	{
		int i = U[g];
		int j = V[g];

		edges[ g ] = {i , j};
	}

	for(int g = 0 ; g < N - 1 ; g++)
		question.push_back( 0 );

	lli dist = ask( question );

	for(int g = 0 ; g < N - 1 ; g++)
	{
		question[ g ] = 1;

		lli aux = ask( question );

		if(dist != aux) inPath[ g ] = true;

		question[ g ] = 0;
	}

	for(int g = 0 ; g < N - 1 ; g++)
	{
		if(inPath[ g ])
		{
			degree[ edges[g].first ]++;
			degree[ edges[g].second ]++; 
		}
	}

	vector<int> ans;

	for(int g = 0 ; g < N ; g++)
		if(degree[g] == 1) ans.push_back( g );

	answer(ans[0] , ans[1]);
}

/*int main()
{
	int nn;
	scanf("%d",&nn);

	vector<int> uu(nn), vv(nn);

	for(int g = 0 ; g < nn - 1 ; g++)
		scanf("%d %d",&uu[g],&vv[g]);

	find_pair(nn , uu , vv , 0 , 0);
}*/

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