Submission #383677

#	Time	Username	Problem	Language	Result	Execution time	Memory
383677		aarr	Dreaming (IOI13_dreaming)	C++14	100 / 100	128 ms	15084 KiB

dreaming

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

const int N = 100 * 1000 + 5;
const int inf = 2000 * 1073 * 1000;

int d1[N], d2[N], d3[N];
vector <int> cmp, vec;
vector <pair <int, int> > adj[N];
//bool mark[N];

void dfs(int v, int* dis) {
	cmp.push_back(v);
	for (auto p : adj[v]) {
		int u = p.first, w = p.second;
		if (dis[u] == inf) {
			int u = p.first, w = p.second;
			dis[u] = dis[v] + w;
			dfs(u, dis);
		}
	}
}

int f(int v, int* dis) {
	cmp.clear();
	dis[v] = 0;
	dfs(v, dis);
	int maxi = v;
	for (auto x : cmp) {
		if (dis[x] > dis[maxi]) {
			maxi = x;
		}
	}
	return maxi;
}

int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
	for (int i = 0; i <= n; i++) {
		d1[i] = d2[i] = d3[i] = inf;
	}
    for (int i = 0; i < m; i++) {
    	int u = A[i], v = B[i], w = T[i];
    	adj[u].push_back({v, w});
    	adj[v].push_back({u, w});
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (d1[i] == inf) {
			int u = f(i, d1);
			int v = f(u, d2);
			ans = max(ans, d2[v]);
			f(v, d3);
			if (cmp.size() == n) {
				return d2[v];
			}
			int mini = i, mnv = max(d2[i], d3[i]);
			for (auto x : cmp) {
				if (max(d2[x], d3[x]) < mnv) {
					mnv = max(d2[x], d3[x]);
					mini = x;
				}
			}
			vec.push_back(mnv);
		//	cout << "73 " << mini << " " << mnv << endl;
		}
	}
	sort(vec.begin(), vec.end());
	int k = vec.size();
	ans = max(ans, vec[k - 1] + vec[k - 2] + l);
	if (k > 2) {
		ans = max(ans, vec[k - 2] + vec[k - 3] + l * 2);
	}
	return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int*)':
dreaming.cpp:16:20: warning: unused variable 'w' [-Wunused-variable]
   16 |   int u = p.first, w = p.second;
      |                    ^
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:54:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |    if (cmp.size() == n) {
      |        ~~~~~~~~~~~^~~~
dreaming.cpp:57:8: warning: variable 'mini' set but not used [-Wunused-but-set-variable]
   57 |    int mini = i, mnv = max(d2[i], d3[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