Submission #299305

#	Time	Username	Problem	Language	Result	Execution time	Memory
299305		Bill_00	Dreaming (IOI13_dreaming)	C++14	100 / 100	129 ms	16760 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#define pb push_back
#define mp make_pair
using namespace std;
int n, m, L;
vector<pair<int, long long> > adj[100005];
bool vis[100005] = {0};
long long p = 0, res = 0;
int id = 0;
vector<long long > a;
void dfs(int u, int x, long long path)
{
	if(path >= p)
	{
		p = path;
		id = u;
	}
	vis[u] = 1;
	for(int i = 0; i < adj[u].size(); i++){
		int v = adj[u][i].first;
		long long e = adj[u][i].second;
		if(v != x) dfs(v, u, path + e);
	} 
}
int go[100005];
long long cost[100005];
void dfsd(int u, int x){
	if(cost[u] >= p)
	{
		p = cost[u];
		id = u;
	}
	go[u] = x;
	for(int i = 0; i < adj[u].size(); i++)
	{
		int v = adj[u][i].first;
		long long e = adj[u][i].second;
		if(v != x)
		{
			cost[v] = cost[u] + e;
			dfsd(v, u);
		}
	}
}
int travelTime(int n,int m,int L,int A[],int B[],int C[])
{
	int i, j;
	cin >> n >> m >> L;
	for(int i=0;i<m;i++)
	{
		adj[A[i]].pb(mp(B[i], C[i]));
		adj[B[i]].pb(mp(A[i], C[i]));
	}
	for(i = 0; i < n; i++)
	if(!vis[i]){
		id = 0;
		p = 0;
		dfs(i, -1, 0);
		dfsd(id, -1);
		long long W = 1e12;
		res = max(res, p);
		int u = id;
		while(u != -1)
		{
			W = min(W, max(cost[u], p - cost[u]));
			u = go[u];
		}
		a.pb(W);
	}
	sort(a.begin(), a.end());
	int sz = a.size();
	if(sz >= 2) res = max(res, a[sz - 1] + a[sz - 2] + L);
	if(sz > 2) res = max(res, a[sz - 2] + a[sz - 3] + 2 * L);
	return res; 
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int, long long int)':
dreaming.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i = 0; i < adj[u].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfsd(int, int)':
dreaming.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i = 0; i < adj[u].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:48:9: warning: unused variable 'j' [-Wunused-variable]
   48 |  int i, j;
      |         ^

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