Submission #881984

#	Time	Username	Problem	Language	Result	Execution time	Memory
881984		serifefedartar	Dreaming (IOI13_dreaming)	C++17	0 / 100	46 ms	29268 KiB

dreaming

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

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 21;
const ll MAXN = 1e5 + 10000;

vector<vector<pair<int,int>>> graph;
int vis[MAXN], up[MAXN], mx[MAXN];
pair<int,int> st[MAXN];
int dfs(int node, int parent) {
	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		int Q = u.s + dfs(u.f, node);
		if (Q > st[node].f)
			st[node] = {Q, st[node].f};
		else if (Q > st[node].s)
			st[node] = {st[node].f, Q};
	}
	return st[node].f;
}

void dfs2(int node, int parent, int par_len) {
	vis[node] = true;
	if (node != parent) {
		int th = st[node].f + par_len;
		up[node] = up[parent] + par_len;
		if (th == st[parent].f)
			up[node] = max(up[node], st[parent].s + par_len);
		else
			up[node] = max(up[node], st[parent].f + par_len);
	}
	mx[node] = max(up[node], st[node].f);

	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		dfs2(u.f, node, u.s);
	}
}

int mx_node = 0, mx_dist = -1;
void dfs3(int node, int parent, int dist) {
	if (dist > mx_dist) {
		mx_dist = dist;
		mx_node = node;
	}

	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		dfs3(u.f, node, dist + u.s);
	}
}

int diameter(int node) {
	mx_dist = -1, mx_node = 0;
	dfs3(node, node, 0);
	int q = mx_node;
	dfs3(q, q, 0);
	return mx_dist;
}

int nd = 0;
void dfs4(int node, int parent) {
	vis[node] = true;
	if (mx[node] > nd)
		nd = mx[node];
	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		dfs4(u.f, node);
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	graph = vector<vector<pair<int,int>>>(N+1, vector<pair<int,int>>());
	for (int i = 0; i < M; i++) {
		graph[A[i]].push_back({B[i], T[i]});
		graph[B[i]].push_back({A[i], T[i]});
	}

	for (int i = 1; i <= N; i++) {
		if (!vis[i]) {
			dfs(i, i);
			dfs2(i, i, 0);
		}
	}

	for (int i = 1; i <= N; i++)
		vis[i] = false;
	priority_queue<pair<int,int>> pq;
	for (int i = 1; i <= N; i++) {
		if (!vis[i]) {
			int dia = diameter(i);
			nd = 0;
			dfs4(i, i);
			pq.push({nd, dia});
		}
	}

	while (pq.size() >= 2) {
		pair<int,int> A = pq.top();
		pq.pop();
		pair<int,int> B = pq.top();
		pq.pop();
		
		int new_dia = max(A.s, max(B.s, A.f + B.f + L));
		int new_mx = min(max(A.f, B.f + L), max(A.f + L, B.f));
		pq.push({new_mx, new_dia});
	}

	cout << pq.top().s << "\n";
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:120:1: warning: no return statement in function returning non-void [-Wreturn-type]
  120 | }
      | ^

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