Submission #198681

#	Time	Username	Problem	Language	Result	Execution time	Memory
198681		arnold518	Dreaming (IOI13_dreaming)	C++14	100 / 100	198 ms	17776 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int INF = 987654321;

int N, M, L;
vector<pii> adj[MAXN+10];

bool vis[MAXN+10];
int DA[MAXN+10], DB[MAXN+10], ans;

void dfs(int now, int bef, int *dist, int dep, vector<int> &V)
{
	dist[now]=dep; vis[now]=true; V.push_back(now);
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		dfs(nxt.first, now, dist, dep+nxt.second, V);
	}
}

int travelTime(int _N, int _M, int _L, int _A[], int _B[], int _T[])
{
	int i, j;
	N=_N; M=_M; L=_L;
	for(i=0; i<M; i++)
	{
		int u=_A[i]+1, v=_B[i]+1, w=_T[i];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}

	vector<int> S;
	for(i=1; i<=N; i++)
	{
		if(vis[i]) continue;
		int u, v; vector<int> V;

		V.clear(); dfs(i, i, DA, 0, V);
		u=i; for(auto it : V) if(DA[u]<DA[it]) u=it;
		
		V.clear(); dfs(u, u, DA, 0, V);
		v=u; for(auto it : V) if(DA[v]<DA[it]) v=it;

		V.clear(); dfs(v, v, DB, 0, V);

		ans=max(ans, DB[u]);

		int now=INF;
		for(auto it : V) now=min(now, max(DA[it], DB[it]));
		S.push_back(now);
	}
	sort(S.begin(), S.end(), greater<int>());
	if(S.size()>=2) ans=max(ans, S[0]+S[1]+L);
	if(S.size()>=3) ans=max(ans, S[1]+S[2]+L+L);
	return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:30:9: warning: unused variable 'j' [-Wunused-variable]
  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