Submission #349691

#	Time	Username	Problem	Language	Result	Execution time	Memory
349691		NachoLibre	Dreaming (IOI13_dreaming)	C++14	100 / 100	150 ms	18668 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) {
	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);
			int l = v[dg][i].second;
			if(p.first + l > dr.first) dr = {p.first + l, p.second};
		}
	}
	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];
			int l = v[dg][i].second;
			if(x + l > dp[dg][1]) {
				dp[dg][2] = dp[dg][1];
				dp[dg][1] = x + l;
				dp[dg][0] = v[dg][i].first;
			} else if(x + l > dp[dg][2]) {
				dp[dg][2] = x + l;
			}
		}
	}
}

int ovox(int dg, int op) {
	// cout << "[2] " << dg << " " << dp[dg][0] << " " << dp[dg][1] << " " << dp[dg][2] << " " << dp[dg][3] << "\n";
	int dr = max(dp[dg][1], dp[dg][3]);
	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;
			int y = ovox(v[dg][i].first, dg);
			dr = (dr > y ? y : dr);
		}
	}
	return dr;
}

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(i, -1).second, -1);
			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(i, -1);
			int b = ovox(i, -1);
			// cout << "[1] " << a << " " << b << "\n";
			assert(a == b);
			wv.push_back(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);
	int a[] = {0,8,2,5,5,1,1,10};
	int b[] = {8,2,7,11,1,3,9,6};
	int c[] = {4,2,4,3,7,1,5,3};
	cout << travelTime(12, 8, 2, a, b, c) << endl;
	return 0;
}
#endif

Compilation message (stderr)

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