Submission #271496

#	Time	Username	Problem	Language	Result	Execution time	Memory
271496		anubhavdhar	Dreaming (IOI13_dreaming)	C++11	100 / 100	164 ms	17016 KiB

dreaming

#include<bits/stdc++.h>

#include "dreaming.h"

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first 
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double

using namespace std;
/*
const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;

const ldd PI = acos(-1);
const ldd EPS = 1e-7;

const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 5;
const ll ROOTN = 320;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;*/

#define INF 1000000000000000006
#define MAXN 100005

ll N, M, cen, mxdep, par[MAXN], ext1, ext2, depth[MAXN], K;
vll g[MAXN];
bool vis[MAXN];

void dfs1(int a, int dep)
{
	if(mxdep < dep)
		mxdep = dep, ext1 = a;
	for(pll bb : g[a])
		if(!vis[bb.ff])
			vis[bb.ff] = true, dfs1(bb.ff, dep + bb.ss);
}

void dfs2(int a, int p, int dep)
{
	// cerr<<a<<' ';
	if(mxdep < dep)
		mxdep = dep, ext2 = a;
	par[a] = p;
	depth[a] = dep;
	for(pll bb : g[a])
		if(bb.ff != p)
			dfs2(bb.ff, a, bb.ss + dep);
}

void dfs3(int a)
{
	if(a == -1)
		return;
	if(mxdep > max(depth[a], depth[ext2] - depth[a]))
		mxdep = max(depth[a], depth[ext2] - depth[a]), cen = a;
	dfs3(par[a]);
}

vi Lenghts;

int solve()
{
	F0R(i, N)
		vis[i] = false;

	ll tt = 0;

	F0R(i, N)
	{
		if(!vis[i])
		{
			// cerr<<"not cisited["<<i<<"]\n";
			vis[i] = true;
			mxdep = -1;
			dfs1(i, 0);
			mxdep = -1;
			dfs2(ext1, -1, 0);
			tt = max(tt, mxdep);
			mxdep = INF;
			dfs3(ext2);
			Lenghts.pb(mxdep);
			// cerr<<"\nmxdep = "<<mxdep<<", ext1 = "<<ext1<<", ext2 = "<<ext2<<'\n';
		}
	}

	sort(all(Lenghts), greater<ll>());
	ll ans;
	if((int)Lenghts.size() == 1)
		ans = Lenghts[0];
	else if ((int)Lenghts.size() == 2)
		ans = Lenghts[1] + Lenghts[0] + K;
	else
		ans = max(Lenghts[1] + K + Lenghts[0], Lenghts[1] + K + K + Lenghts[2]);
	return max(tt, ans);
}

int travelTime(int n, int m, int L, int A[], int B[], int T[])
{
	N = n;
	M = m;
	K = L;
	F0R(i, M)
		g[A[i]].pb(mp(B[i], T[i])), g[B[i]].pb(mp(A[i], T[i]));
	return solve();
}
/*
signed main()
{

	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	

	int n, m, L;
	cin>>n>>m>>L;
	int A[m], B[m], T[m];

	F0R(i, m)
		cin>>A[i]>>B[i]>>T[i];

	cout<<travelTime(n, m, L, A, B, T)<<'\n';

	return 0;
}*/

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