Submission #788500

#	Time	Username	Problem	Language	Result	Execution time	Memory
788500		LIF	Dreaming (IOI13_dreaming)	C++14	100 / 100	60 ms	21108 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
#include<vector>
using namespace std;
vector<pair<int,int> > vv[300005];
bool vis1[300005];
bool vis2[300005];
bool vis3[300005];
int dis[300005];
int dis2[300005];
int maxn = -1;
int id1 = 0;
int id2 = 0;
vector<int> temp;
vector<int> r;
int ans1 = -1;//D
int ans2 = -1;//R1+R2+L
int ans3 = -1;//R2+R3+L;
void dfs1(int now)
{
	vis1[now] = true;
	for(int i=0;i<vv[now].size();i++)
	{
		pair<int,int> pp = vv[now][i];
		if(vis1[pp.first] == true)continue;
		dis[pp.first] = dis[now] + pp.second;
		if(dis[pp.first] > maxn)
		{
			maxn = dis[pp.first];
			id1 = pp.first;
		}
		dfs1(pp.first);
	}
	return;
}
void dfs2(int now)
{
	vis2[now] = true;
	for(int i=0;i<vv[now].size();i++)
	{
		pair<int,int> pp = vv[now][i];
		if(vis2[pp.first] == true)continue;
		dis2[pp.first] = dis2[now] + pp.second;
		if(dis2[pp.first] > maxn)
		{
			maxn = dis2[pp.first];
			id2 = pp.first;
		}
		dfs2(pp.first);
	}
	return;
}
bool find_path(int now,int target)
{
	bool can = false;
	temp.push_back(now);
	if(now == target)return true;
	vis3[now] = true;
	for(int i=0;i<vv[now].size();i++)
	{
		pair<int,int> pp = vv[now][i];
		if(vis3[pp.first] == true)continue;
		if(find_path(pp.first,target) == true)can = true;
	}
	if(can == false)
	{
		temp.pop_back();
		return false;
	}
	return true;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for(int i=0;i<M;i++)
	{
		vv[A[i]].push_back(make_pair(B[i],T[i]));
		vv[B[i]].push_back(make_pair(A[i],T[i])); 
	}
	for(int i=0;i<N;i++)
	{
		if(vis1[i] == true)continue;
		temp.clear();
		maxn = -1;
		id1 = -1;
		id2 = -1;
		//be care: if there are only one vertices , id1 -> -1;
		dfs1(i);
		/*cout<<endl;
		cout<<i<<endl;
		for(int j=0;j<N;j++)cout<<dis[j]<<" ";
		cout<<endl;*/
		maxn = -1;
		if(id1 == -1)id1 = i;
		dfs2(id1);
		if(id2 == -1)id2 = i;
		/*cout<<id1<<endl;
		for(int j=0;j<N;j++)cout<<dis2[j]<<" ";
		cout<<endl;*/
		//cout<<endl;
		bool exis = find_path(id1,id2);
		ans1 = max(ans1,dis2[id2]);
		//cout<<ans1<<endl;
		//D;
		int rmin = 1e9;
		for(int j=0;j<temp.size();j++)
		{
			int val = max(dis2[temp[j]],dis2[id2] - dis2[temp[j]]);
			rmin = min(rmin,val);
		}
		r.push_back(rmin);
	}
	sort(r.begin(),r.end());
	if(r.size() >= 2)ans2 = (r[r.size()-1] + r[r.size()-2] + L);
	if(r.size() >= 3)ans3 = (r[r.size()-2] + r[r.size()-3] + L*2);

    return max(ans1,max(ans2,ans3));
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs1(int)':
dreaming.cpp:22:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i=0;i<vv[now].size();i++)
      |              ~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int)':
dreaming.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=0;i<vv[now].size();i++)
      |              ~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'bool find_path(int, int)':
dreaming.cpp:59:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i=0;i<vv[now].size();i++)
      |              ~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:104:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for(int j=0;j<temp.size();j++)
      |               ~^~~~~~~~~~~~
dreaming.cpp:99:8: warning: unused variable 'exis' [-Wunused-variable]
   99 |   bool exis = find_path(id1,id2);
      |        ^~~~

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