Submission #403657

#	Time	Username	Problem	Language	Result	Execution time	Memory
403657		ritul_kr_singh	Dreaming (IOI13_dreaming)	C++17	100 / 100	141 ms	13608 KiB

dreaming

#include <bits/stdc++.h>
using namespace std;
#define sp << ' ' <<
#define nl << '\n'
#include "dreaming.h"

const int MAXN = 1e5, INF = 2e9;

vector<array<int, 2>> g[MAXN];
int a[MAXN], b, x, y, ans = -1;
bitset<MAXN> vis;

void dfs(int u, int d, int p = -1){
	vis[u] = 1;
	a[u] = max(a[u], d);
	if(d > x) x = d, y = u;
	if(d < 0) b = min(b, a[u]);
	for(auto &e : g[u]) if(e[0] != p) dfs(e[0], d < 0 ? d : d + e[1], u);
}

int travelTime(int n, int m, int L, int A[], int B[], int T[]){
	for(int i=0; i<m; ++i){
		g[A[i]].push_back({B[i], T[i]});
		g[B[i]].push_back({A[i], T[i]});
	}
	priority_queue<int> q;
	for(int i=0; i<n; ++i){
		if(vis[i]) continue;
		x = y = -1, b = INF;
		dfs(i, 0), dfs(y, 0), dfs(y, 0);
		ans = max(ans, x);
		dfs(i, -1);
		q.push(-b);
		while(q.size() > 3) q.pop();
	}
	int a3 = -q.top(); q.pop();
	if(q.empty()) return ans;
	int a2 = -q.top(); q.pop();
	if(q.empty()) return max(ans, a2 + a3 + L);
	int a1 = -q.top(); q.pop();
	return max(ans, max(a1 + a2 + L, a2 + a3 + L + L));
}

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