Submission #119194

#	Time	Username	Problem	Language	Result	Execution time	Memory
119194		rajarshi_basu	Dreaming (IOI13_dreaming)	C++14	100 / 100	134 ms	14724 KiB

dreaming

#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <stack>
#include <set>

#include "dreaming.h"

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define vv vector
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>

using namespace std;

const int MAXN = 1e5 + 10;

int dist[MAXN];
bool vis[MAXN];
vv<ii> g[MAXN];
vi now;

void dfs(int node,int p = -1){
	now.pb(node);
	for(auto e : g[node]){
		if(e.ff == p)continue;
		dfs(e.ff,node);
	}
}

void dfsdist(int node,int p = -1){
	vis[node] = 1;
	for(auto e:g[node]){
		if(e.ff == p)continue;
		dist[e.ff] = e.ss + dist[node];
		dfsdist(e.ff,node);
	}
}

int ans; 
vi path;
void dfs2(int node,int target,int p=-1){
	if(node == target){
		// we now process our path variable
		ans = dist[target];
		//cout << node << " " << target << " : " << dist[target] << endl;
		int sum = 0;
		for(auto e:path){
			sum += e;
		//	cout << sum << " [] ";
			ans = min(ans,max(sum,dist[target]-sum));
		}
		//cout << endl;
	}
	for(auto e : g[node]){
		if(e.ff == p)continue;
		path.pb(e.ss);
		dfs2(e.ff,target,node);
		path.pop_back();
	}
}

int travelTime(int n,int m,int l,int a[],int b[],int t[]){
	if(m == 0){
		if(n == 1)return 0;
		if(n == 2)return l;
		return 2*l;
	}
	if(m == 1){
		if(n == 2)return t[0];
		if(n == 3)return l+t[0];
		return max(l+t[0], 2*l);
	}
	// lets prove lemma 1
	vector<int> t2;
	FOR(i,m){
		g[a[i]].pb({b[i],t[i]});
		g[b[i]].pb({a[i],t[i]});
	}
	//cout << "bleh" << endl;
	int MXD = 0;
	FOR(i,n){
		if(vis[i])continue;
		// this is a new component.
		now.clear();
	//	cout << i << endl;
		dfs(i);
		dist[i] = 0;
		dfsdist(i);
		int mxd = 0;
		int ele = now[0];
		for(auto e : now){
			if(dist[e] > mxd){
				mxd = dist[e];
				ele = e;
			}
		}
		dist[ele] = 0;
		dfsdist(ele);
		for(auto e:now){
			MXD = max(MXD,dist[e]);
		}
		mxd = 0;
		int elec = ele;
		for(auto e : now){
			if(dist[e] > mxd){
				mxd = dist[e];
				ele = e;
			}
		}
	//	cout << elec << " " << ele << endl;
		
		path.clear();
		dfs2(elec,ele);
		t2.pb(ans);
		continue;
	/*	for(auto e : now){
			cout << e << " ";
		}
		*/
	//	cout << "ok" << endl;
		int mn = -1;
		for(auto e:now){
		//	cout << e << endl;
			dist[e] = 0;
			dfsdist(e);
			int mx = 0;
			FOR(j,now.size()){
				mx = max(mx,dist[now[j]]);
			}

			if(mn == -1)mn = mx;
			else mn = min(mn,mx);
		}
		//cout << endl;
		t2.pb(mn);
	}



	// this is the 18 pnts substask, will be useful later.
	/*
	for(auto e : t2){
		cout << e << " ";
	}
	cout << endl;
	*/
	sort(t2.begin(), t2.end());
	reverse(t2.begin(), t2.end());
	/*
	for(auto e : t2){
		cout << e << " ";
	}
	cout << endl;
	*/
	if(t2.size() == 1)return MXD;
	int mx = (t2[0] + l + t2[1]);
	//cout << mx << endl;
	if(t2.size() == 2)return max(MXD,mx);
	//while(1);
	mx = max(t2[1] + l + l + t2[2],mx);
	return max(MXD,mx);
}

int ma1in(){
	int n = 12;
	int m = 8;
	int l = 2;
	int a[8] = {0,8,2,5,5,1,1,10};
	int b[8] = {8,2,7,11,1,3,9,6};
	int t[8] = {4,2,4,3,7,1,5,3};
	cout << travelTime(n,m,l,a,b,t) << endl;


	return 0;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:19:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,n) for(int i=0;i<n;i++)
dreaming.cpp:149:8:
    FOR(j,now.size()){
        ~~~~~~~~~~~~            
dreaming.cpp:149:4: note: in expansion of macro 'FOR'
    FOR(j,now.size()){
    ^~~

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