Submission #651320

#	Time	Username	Problem	Language	Result	Execution time	Memory
651320		therealpain	Dreaming (IOI13_dreaming)	C++14	32 / 100	73 ms	14072 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h> 
#define fi first 
#define se second
#define mp make_pair
#define getbit(x, i) (((x) >> (i)) & 1)
#define all(x) x.begin(), x.end()
#define TASK "DREAMING"
 
using namespace std;
 
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
 
const long long inf = 1e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 7;

long long dp[N][2], g[N], d[N], ans;
pair <long long, int> center_dist;
vector <pair <int, int>> a[N];
bool visited[N];
int n, m, l;

void dfs1(int u, int p) {
	visited[u] = 1;
	for (auto i : a[u]) {
		if (i.fi == p) continue;
		int v = i.fi, w = i.se;
		dfs1(v, u);
		if (dp[u][0] < dp[v][0] + w) {
			dp[u][1] = dp[u][0];
			dp[u][0] = dp[v][0] + w;
		} else if (dp[v][0] + w > dp[u][1]) 
			dp[u][1] = dp[v][0] + w; 
	}
	maxi(ans, dp[u][0] + dp[u][1]);
}

void dfs2(int u, int p, long long w) {
	if (p != u) g[u] = max(g[p] + w, (dp[u][0] + w == dp[p][0] ? (dp[p][1] + w) : dp[p][0]));
	mini(center_dist, mp(max(g[u], dp[u][0]),  u));
	for (auto i : a[u]) {
		if (i.fi == p) continue;
		int v = i.fi, w2 = i.se;
		dfs2(v, u, w2); 
	} 
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n = N;
    m = M;
    l = L;
	for (int i = 0; i < m; ++i) {
		int u = ++A[i], v = ++B[i], w = T[i]; 
		a[u].push_back({v, w});
		a[v].push_back({u, w});
	}
	vector <pair <int, int>> v;
	for (int i = 1; i <= n; ++i) {
		if (visited[i] == 1) continue;
		dfs1(i, i);
		center_dist = mp(1e9 + 9, 0); 
		dfs2(i, i, 0);
		v.push_back(center_dist);
	}
	sort(all(v), greater <pair <int, int>>());
	for (int i = 1; i < v.size(); ++i) {
		a[v[0].se].emplace_back(v[i].se, l);
		a[v[i].se].emplace_back(v[0].se, l);
	}
	memset(dp, 0, sizeof dp);
	ans = 0;
	dfs1(1, 1);
	return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for (int i = 1; i < v.size(); ++i) {
      |                  ~~^~~~~~~~~~

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