Submission #198762

#	Time	Username	Problem	Language	Result	Execution time	Memory
198762		maximath_1	Dreaming (IOI13_dreaming)	C++11	100 / 100	143 ms	17272 KiB

dreaming

#include"dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int> >adj[100005];
vector<int>v;
bool vis[100005];
int par[100005], X[100005];
pair<int, int> dfs(int nw, int bf){
	pair<int, int> rs={0, nw};
	for(pair<int, int> i:adj[nw]){
		if(i.second==bf) continue;
		pair<int, int> rst=dfs(i.second, nw);
		rs=max(rs, {rst.first+i.first, rst.second});
	}
	X[nw]=rs.first;
	par[nw]=bf; vis[nw]=true;
	return rs;
}
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({T[i], B[i]});
		adj[B[i]].push_back({T[i], A[i]});
	}
	int ans, diameter=0;
	for(int i=0; i<n; i++){
		if(vis[i]) continue;
		pair<int, int> rs=dfs(dfs(i, i).second, -1);
		int nd=rs.second, mn=rs.first;
		for(; nd>=0; nd=par[nd]) mn=min(mn, max(X[nd], rs.first-X[nd]));
		v.push_back(mn); diameter=max(diameter, rs.first);
	}
	sort(v.begin(), v.end()); reverse(v.begin(), v.end());
	if(v.size()>2){
		ans=L+v[0]+v[1];
		for(int i=2; i<v.size(); i++)
			ans=max(ans, 2*L+v[1]+v[i]);
	}else if(v.size()==2) ans=L+v[0]+v[1];
	else ans=0;
	ans=max(ans, diameter);
	return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=2; i<v.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