Submission #224782

#	Time	Username	Problem	Language	Result	Execution time	Memory
224782		nafis_shifat	Dreaming (IOI13_dreaming)	C++14	100 / 100	148 ms	24028 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int mxn=1e5+6;

vector<int> adj[mxn];
vector<int> cost[mxn];

int m1[mxn]={};
int m2[mxn]={};
int u1[mxn];

int ans=0;
int vis[mxn]={};
void dfs(int cur,int prev)
{
	vis[cur]=1;
	for(int i=0;i<adj[cur].size();i++)
	{
		int v=adj[cur][i];
		int c=cost[cur][i];
		if(v==prev)continue;

		dfs(v,cur);
		int k=m1[v]+c;

		if(k>m1[cur])
		{
			m2[cur]=m1[cur];
			m1[cur]=k;
			u1[cur]=v;
		}
		else if(k>m2[cur])
			m2[cur]=k;
		
		

	}
}
vector<int> v;
void calc(int cur,int prev,int cst)
{

	v.push_back(max(cst,m1[cur]));
	ans=max(ans,cst+m1[cur]);

	for(int i=0;i<adj[cur].size();i++)
	{
		int v=adj[cur][i];
		int c=cost[cur][i];

		if(v==prev)continue;

		int tmp=cst+c;

		if(v==u1[cur])tmp=max(tmp,m2[cur]+c);
		else tmp=max(tmp,m1[cur]+c);
		calc(v,cur,tmp);
	}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
	for(int i=0;i<M;i++)
	{
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);

		cost[A[i]].push_back(T[i]);
		cost[B[i]].push_back(T[i]);
	}


	vector<int> fn;

	for(int i=0;i<N;i++)
	{
		if(vis[i])continue;
		dfs(i,-1);

		calc(i,-1,0);

		sort(v.begin(),v.end());
		fn.push_back(v[0]);

		v.clear();
		


	}
	sort(fn.begin(),fn.end(),greater<int>());
   
	if(fn.size()>1)
	{
		ans=max(ans,fn[0]+fn[1]+L);
	}
	if(fn.size()>2)
	{
		ans=max(ans,fn[1]+fn[2]+2*L);
	}

	return ans;

}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[cur].size();i++)
              ~^~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void calc(int, int, int)':
dreaming.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[cur].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