Submission #489143

#	Time	Username	Problem	Language	Result	Execution time	Memory
489143		ssense	Dreaming (IOI13_dreaming)	C++14	100 / 100	98 ms	18096 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define nax 200005
#define pb push_back
#define sc second
#define fr first
//#define int unsigned long long
//#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl

 
vector<vector<pair<int, int>>> adj;
vector<bool> vis;

int bfs(int s)
{
	queue<pair<pair<int, int>, int>> q;
	q.push({{s, -1}, 0});
	int now = 0;
	while(!q.empty())
	{
		int node = q.front().fr.fr;
		int dist = q.front().sc;
		int parent = q.front().fr.sc;
		if(adj[node].size() == 1)
		{
			now = max(now, dist);
		}
		q.pop();
		for(auto v : adj[node])
		{
			if(v.fr != parent)
			{
				q.push({{v.fr, node}, dist+v.sc});
			}
		}
	}
	return now;
}
 

pair<int, int> dfsnow(int u, int p)
{
	int mxnod = u, mxdist = 0;
	vis[u] = true;
	for(auto v : adj[u])
	{
		if(v.fr != p)
		{
			pair<int, int> now = dfsnow(v.fr, u);
			if(now.sc+v.sc > mxdist)
			{
				mxdist = max(mxdist, now.sc+v.sc);
				mxnod = now.fr;
			}
		}
	}
	return {mxnod, mxdist};
}



int globb;

vector<pair<int, int>> pathdiametru;
bool fnd = false;
void dfs2(int u, int p, int dist)
{
	if(fnd)
	{
		return;
	}
	pathdiametru.pb({u, dist});
	if(u == globb)
	{
		fnd = true;
		return;
	}
	for(auto v : adj[u])
	{
		if(fnd)
		{
			return;
		}
		if(v.fr != p)
		{
			dfs2(v.fr, u, dist+v.sc);
		}
	}
	if(fnd)
	{
		return;
	}
	pathdiametru.pop_back();
}

pair<pair<int, int>, int> get(int u)
{
	int endpoint_a = dfsnow(u, -1).fr;
	pair<int, int> path = dfsnow(dfsnow(u, -1).fr, -1);
	int endpoint_b = path.fr;
	globb = endpoint_b;
	fnd = false;
	pathdiametru.clear();
	int dist = path.sc;
	dfs2(endpoint_a, -1, 0);
	//assert(dist == pathdiametru.back().sc);
	int best;
	for(int i = 0; i < pathdiametru.size(); i++)
	{
		if(pathdiametru[i].sc > dist/2)
		{
			if(max(pathdiametru[i-1].sc, dist-pathdiametru[i-1].sc) < pathdiametru[i].sc)
			{
				best = pathdiametru[i-1].fr;
			}
			else
			{
				best = pathdiametru[i].fr;
			}
			break;
		}
	}
	return {{best, bfs(best)}, dist};
}
 
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
	if(n == 1)
	{
		return 0;
	}
	adj.clear();
	for(int i = 0; i < n; i++)
	{
		vector<pair<int, int>> cop;
		adj.pb(cop);
	}
	vis.assign(n+1, false);
	for(int i = 0; i < m; i++)
	{
		adj[a[i]].pb({b[i], t[i]});
		adj[b[i]].pb({a[i], t[i]});
	}
	int ans = 0;
	int mxalready = 0;
	vint mx;
	for(int i = 0; i < n; i++)
	{
		if(!vis[i])
		{
			pair<pair<int, int>, int> now = get(i);
			mx.pb(now.fr.sc);
			mxalready = max(mxalready, now.sc);
		}
	}
	sort(all(mx));
	int ans2 = 0;
	if(mx.size() > 2)
	{
		ans2+=mx[mx.size()-2]+mx[mx.size()-3]+2*l;
	}
	ans+=mx[mx.size()-1];
	ans+=mx[mx.size()-2];
	ans+=l;
	return max({ans, mxalready, ans2});
}
/*
int main()
{
	int n, m, l;
	cin >> n >> m >> l;
	int a[m], b[m], t[m];
	for(int i = 0; i < m; i++)
	{
		cin >> a[i] >> b[i] >> t[i];
	}
	cout << travelTime(n, m, l, a, b, t) << endl;
}
*/
/*
 7 5 2
 0 1 10
 0 5 5
 5 4 6
 3 2 2
 2 6 1
 
 8 6 3
 0 1 1
 1 2 1
 1 3 1
 1 4 10
 4 5 10
 6 7 7
 
 2 0 2
 
 3 1 10
 1 2 1
 
 9 7 2
 0 1 4
 1 2 2
 2 3 4
 4 5 1
 5 6 5
 5 7 7
 7 8 3
 
 8 6 2
 0 1 2
 1 2 3
 2 3 2
 3 4 10
 5 6 10
 6 7 1
 */

Compilation message (stderr)

dreaming.cpp: In function 'std::pair<std::pair<int, int>, int> get(int)':
dreaming.cpp:121:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |  for(int i = 0; i < pathdiametru.size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:136:20: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
  136 |  return {{best, bfs(best)}, dist};
      |                 ~~~^~~~~~

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