Submission #154027

#	Time	Username	Problem	Language	Result	Execution time	Memory
154027		emaborevkovic	Dreaming (IOI13_dreaming)	C++14	100 / 100	163 ms	16068 KiB

dreaming

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <dreaming.h>

using namespace std;

#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define trace(x) cerr << #x << " " << x << endl

const int N = 1e5+11;
int n, m, l;
vector <pair <int, int> > ls[N];
int bio[N];
pair <int, int> maxi;
pair <int, int> mama[N];
int res = 0;
vector <int> v;

void dfs (int x, int dalj) {
	bio[x] = 1;
	maxi = max(maxi, mp(dalj, x));
	for (int i=0;i<ls[x].size();i++) {
		if (bio[ls[x][i].ff]) continue;
		dfs(ls[x][i].ff, dalj + ls[x][i].ss);
	}
}

void dfss (int x, int p, int dalj) {
	maxi = max(maxi, mp(dalj, x));
	mama[x].ff = p;
	for (int i=0;i<ls[x].size();i++) {
		if (ls[x][i].ff == p) {
			mama[x].ss = ls[x][i].ss;
			continue;
		}
		dfss (ls[x][i].ff, x, dalj+ls[x][i].ss);
	}
}

int gore (int x, int dalj, int dm) {
	int ret = max(dalj, dm-dalj);
	if (mama[x].ff == -1) return ret;
	ret = min(ret, gore (mama[x].ff, dalj+mama[x].ss, dm));
	return ret;
}

int travelTime (int n, int m, int l, int a[N], int b[N], int t[N]) {
	for (int i=0;i<m;i++) {
		ls[a[i]].pb(mp(b[i], t[i]));
		ls[b[i]].pb(mp(a[i], t[i]));
	}
	for (int i=0;i<n;i++) {
		maxi = mp(0, 0);
		if (bio[i]) continue;
		dfs(i, 0);
		int x = maxi.ss;
		maxi = mp(0, 0);
		dfss(x, -1, 0);
		int y = maxi.ss;
		int dm = maxi.ff;
		res = max(res, dm);
		v.pb(gore(y, 0, dm));
 	}
 	sort (v.begin(), v.end());
 	int s = v.size();
 	if (s >= 2) {
 		res = max(res, v[s-1]+v[s-2]+l);
	}
	if (s >= 3) {
	 	res = max(res, v[s-2]+v[s-3]+2*l);
	}
	return res;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<ls[x].size();i++) {
               ~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfss(int, int, int)':
dreaming.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<ls[x].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