Submission #139423

#	Time	Username	Problem	Language	Result	Execution time	Memory
139423		Kenzo_1114	Highway Tolls (IOI18_highway)	C++14	5 / 100	33 ms	10540 KiB

highway

#include<bits/stdc++.h>
#include "highway.h"
using namespace std;
const int MAXN=200010;

int marc[MAXN],dist[MAXN];
vector<int>  grafo[MAXN],grafo2[MAXN];
pair<int,int> edge[MAXN];

/*
long long int ask(vector<int> aux)
{
	printf("ASK : ");
	for(int i=0;i<aux.size();i++)	printf("%d",aux[i]);
	printf("\n");
	
	long long int val;
	scanf("%lld",&val);
	return val;
}
*/


void dfs(int v,int ind)
{
	marc[v]=ind;
	for(int i=0;i<grafo2[v].size();i++)
	{
		int viz=grafo2[v][i];
		if(marc[viz]==ind)	continue;
		dist[viz]=dist[v]+1;
		dfs(viz,ind);
	}
}

void find_pair(int n,vector<int> u,vector<int> v,int a,int b)
{
	vector<int> w;
	for(int i=0;i<u.size();i++)	w.push_back(0);
	long long int aux=ask(w);
	
	for(int i=0;i<u.size();i++)
	{
		grafo[u[i]].push_back(v[i]);
		grafo[v[i]].push_back(u[i]);
		edge[i]=make_pair(u[i],v[i]);
	}
	
	for(int i=0;i<u.size();i++)
	{
		w[i]=1;
		if(ask(w)>aux)
		{
			int a=edge[i].first;
			int b=edge[i].second;
			grafo2[a].push_back(b);
			grafo2[b].push_back(a);
		}
		w[i]=0;
	}
	
	long long int resp=0, s,t;
	for(int i=0;i<n;i++)
	{
		dfs(i,i+1);
		for(int j=0;j<n;j++)
		{
			if(resp<dist[j])
				resp=dist[j],	s=i, t=j;	
		}
		memset(dist,0,sizeof(dist));
	}
	
//	printf("%lld %lld\n",s,t);
	answer(s,t);
}

/*
int main ()
{
	int m,n,a,b;
	vector<int> u,v;
	
	scanf("%d %d",&n,&m);
	
	for(int i=0;i<m;i++)
		scanf("%d %d",&a,&b),	u.push_back(a),	v.push_back(b);
		
	scanf("%d %d",&a,&b);	
	
	find_pair(n,u,v,a,b);

}
*/

/*
7 6
0 1
1 2
2 3
3 4
4 5
5 6
1 10

*/

Compilation message (stderr)

highway.cpp: In function 'void dfs(int, int)':
highway.cpp:27:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<grafo2[v].size();i++)
              ~^~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:39:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++) w.push_back(0);
              ~^~~~~~~~~
highway.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++)
              ~^~~~~~~~~
highway.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++)
              ~^~~~~~~~~
highway.cpp:75:8: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  answer(s,t);
  ~~~~~~^~~~~
highway.cpp:75:8: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]

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