Submission #211196

#	Time	Username	Problem	Language	Result	Execution time	Memory
211196		mode149256	Dreaming (IOI13_dreaming)	C++14	18 / 100	71 ms	12152 KiB

dreaming

/*input

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

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}

vb been;
int last;
int longest;
int puse;
vpi edges[MX];

void dfs(int x, int prev, int dis) {
	if (dis > longest) {
		longest = dis;
		last = x;
	}

	for (auto u : edges[x])
		if (u.x != prev)
			dfs(u.x, x, dis + u.y);
}

void dfs(int x) {
	been[x] = true;
	for (auto u : edges[x])
		if (!been[u.x])
			dfs(u.x);
}

bool raskPuse(int x, int prev, int dis) {
	if (dis == longest) return true;
	bool kely = false;

	for (auto u : edges[x])
		if (u.x != prev)
			kely = kely || raskPuse(u.x, x, dis + u.y);

	if (kely) puse = min(puse, max(dis, longest - dis));
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	been = vb(N, false);

	for (int i = 0; i < M; ++i)
	{
		edges[A[i]].emplace_back(B[i], T[i]);
		edges[B[i]].emplace_back(A[i], T[i]);
	}

	vi puses;
	int ats = 0;

	for (int i = 0; i < N; ++i)
	{
		if (been[i]) continue;
		longest = 0;
		last = i;
		dfs(i, -1, 0);
		longest = 0;
		dfs(last, -1, 0);

		puse = longest;
		ats = max(ats, longest);

		raskPuse(last, -1, 0);

		puses.emplace_back(puse);

		dfs(i);
		// printf("i = %d, longest = %d, puse = %d\n", i, longest, puse);
	}

	sort(puses.rbegin(), puses.rend());

	if (puses.size() >= 2) {
		ats = max(ats, puses[0] + L + puses[1]);
	}

	if (puses.size() >= 3) {
		ats = max(ats, puses[1] + L + L + puses[2]);
	}

	return ats;
}

Compilation message (stderr)

dreaming.cpp: In function 'bool raskPuse(int, int, int)':
dreaming.cpp:90:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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