Submission #87992

#	Time	Username	Problem	Language	Result	Execution time	Memory
87992		Pajaraja	Dreaming (IOI13_dreaming)	C++17	100 / 100	167 ms	20548 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> g[100001],t[100001];
int maax,maxind,sol[100001],cnt,n,m,l,maxp[100001];
bool vi[100001];
bool lockdown;
void dfsdist(int s,int f,int dist)
{
	vi[s]=true;
	if(dist>maax) 
	{
	    maax=dist;
	    maxind=s;
	}
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfsdist(g[s][i],s,dist+t[s][i]);
}
void dfs(int s,int f,int dist,int ne)
{
	if(dist==ne) 
	{
	    lockdown=true;
	    sol[cnt]=maax;
	}
	for(int i=0;i<g[s].size();i++) 
	{
	    if(g[s][i]!=f) dfs(g[s][i],s,dist+t[s][i],ne);
	    if(lockdown) 
		{
		    sol[cnt]=fmin(sol[cnt],fmax(maax-dist,dist)); 
		    return;
		}
	}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) 
{
	int t1,t2,t3;
	n=N;
	m=M;
	l=L;
	for(int i=0;i<m;i++)
	{
		t1=A[i];
		t2=B[i];
		t3=T[i];
		g[t1].push_back(t2);
		g[t2].push_back(t1);
		t[t1].push_back(t3);
		t[t2].push_back(t3);
	}
	for(int i=0;i<n;i++) if(!vi[i])
	{
		maax=0;
		maxind=i;
		dfsdist(i,-1,0);
		maax=0;
		dfsdist(maxind,-1,0);
		maxp[cnt]=maax;
		lockdown=false;
		dfs(maxind,-1,0,maax);
		cnt++;
	}
	int rez=0;
	for(int i=0;i<cnt;i++) rez=fmax(rez,maxp[i]);
	sort(sol,sol+cnt);
	if(cnt>1)rez=fmax(rez,sol[cnt-1]+l+sol[cnt-2]);
	if(cnt>2) rez=fmax(rez,sol[cnt-2]+2*l+sol[cnt-3]);
	return rez;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfsdist(int, int, int)':
dreaming.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfsdist(g[s][i],s,dist+t[s][i]);
              ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs(int, int, int, int)':
dreaming.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) 
              ~^~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23