Submission #349679

#	Time	Username	Problem	Language	Result	Execution time	Memory
349679		NachoLibre	Dreaming (IOI13_dreaming)	C++14	0 / 100	113 ms	14160 KiB

dreaming

#include <bits/stdc++.h>
using namespace std;
#ifndef wambule
#include "dreaming.h"
#endif

const int N = 100005;
int dp[N][4];
vector<pair<int, int> > v[N];
vector<int> ve;
bool bo[N];

pair<int, int> ovod(int dg, int op, int mn) {
	bo[dg] = 1;
	pair<int, int> dr = {0, dg};
	for(int i = 0; i < v[dg].size(); ++i) {
		if(v[dg][i].first != op) {
			pair<int, int> p = ovod(v[dg][i].first, dg, mn + v[dg][i].second);
			if(p.first > dr.first) dr = p;
		}
	}
	return dr;
}

void ovog(int dg, int op, int mn, int sv) {
	ve.push_back(mn);
	if(dg == sv) {
		ve[0] = -1;
		return;
	}
	for(int i = 0; i < v[dg].size(); ++i) {
		if(v[dg][i].first != op) {
			ovog(v[dg][i].first, dg, mn + v[dg][i].second, sv);
			if(ve[0] == -1) return;
		}
	}
	ve.pop_back();
}

void ovoq(int dg, int op) {
	dp[dg][0] = dg;
	dp[dg][1] = dp[dg][2] = dp[dg][3] = 0;
	for(int i = 0; i < v[dg].size(); ++i) {
		if(v[dg][i].first != op) {
			ovoq(v[dg][i].first, dg);
			int x = dp[v[dg][i].first][1];
			if(x > dp[dg][1]) {
				dp[dg][2] = dp[dg][1];
				dp[dg][1] = x;
				dp[dg][0] = dp[v[dg][i].first][0];
			} else if(x > dp[dg][2]) {
				dp[dg][2] = x;
			}
		}
	}
}

int ovox(int dg, int op) {
	int dr = 0;
	for(int i = 0; i < v[dg].size(); ++i) {
		if(v[dg][i].first != op) {
			int x = (v[dg][i].first == dp[dg][0] ? dp[dg][2] : dp[dg][1]);
			dp[v[dg][i].first][3] = max(dp[dg][3], x) + v[dg][i].second;
			dr = max(dr, ovox(v[dg][i].first, dg));
		}
	}
	return min(dr, max(dp[dg][1], dp[dg][3]));
}

int travelTime(int n, int m, int l, int a[], int b[], int c[]) {
	for(int i = 0; i < n; ++i) {
		v[i].clear();
		bo[i] = 0;
	}
	for(int i = 0; i < m; ++i) {
		v[a[i]].push_back({b[i], c[i]});
		v[b[i]].push_back({a[i], c[i]});
	}
	int dm = 0;
	vector<int> wv;
	for(int i = 0; i < n; ++i) {
		if(!bo[i]) {
			int x = 0;
			pair<int, int> p = ovod(x = ovod(0, -1, 0).second, -1, 0);
			ve.clear();
			ovog(x, -1, 0, p.second);
			ve[0] = 0;
			int a = p.first;
			dm = max(dm, a);
			for(int i = 1; i < ve.size(); ++i) {
				a = min(a, max(ve[i], p.first - ve[i]));
			}
			ovoq(0, -1);
			int b = ovox(0, -1);
			wv.push_back((assert(a == b), a = b));
		}
	}
	sort(wv.begin(), wv.end());
	reverse(wv.begin(), wv.end());
	int dr = 0;
	if(wv.size() == 1);
	else if(wv.size() == 2) {
		dr = wv[0] + wv[1] + l;
	} else {
		dr = max(wv[0] + wv[1] + l, wv[1] + wv[2] + l + l);
	}
	return max(dm, dr);
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	return 0;
}
#endif

Compilation message (stderr)

dreaming.cpp: In function 'std::pair<int, int> ovod(int, int, int)':
dreaming.cpp:16: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]
   16 |  for(int i = 0; i < v[dg].size(); ++i) {
      |                 ~~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void ovog(int, int, int, int)':
dreaming.cpp:31: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]
   31 |  for(int i = 0; i < v[dg].size(); ++i) {
      |                 ~~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void ovoq(int, int)':
dreaming.cpp:43: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]
   43 |  for(int i = 0; i < v[dg].size(); ++i) {
      |                 ~~^~~~~~~~~~~~~~
dreaming.cpp: In function 'int ovox(int, int)':
dreaming.cpp:60: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]
   60 |  for(int i = 0; i < v[dg].size(); ++i) {
      |                 ~~^~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:90:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |    for(int i = 1; i < ve.size(); ++i) {
      |                   ~~^~~~~~~~~~~

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