| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 881986 | serifefedartar | Dreaming (IOI13_dreaming) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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>, greater<pair<int,int>>, vector<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});
}
return pq.top().s;
}