| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 411290 | 2021-05-25T00:48:19 Z | islander7 | Dreaming (IOI13_dreaming) | C++17 | 0 ms | 0 KB |
#include "dreaming.h"
#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
#define ll long long
#define pii pair <ll, int>
using namespace std;
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
map <int, vector <pii>> adj;
map <int, vector <int>> cc;
map <pii, int> edges;
map <int, int> ccnum;
int maxgrp;
ll maxlen = 0;
map <int, int> roots;
map <int, int> layer;
vector <int> mins;
ll m1 = -1, m2 = -1, m3 = -1;
int N, M, L;
cin >> N >> M >> L;
for (int i = 0; i < M; i++)
{
cin >> A[i] >> B[i] >> T[i];
adj[A[i]].push_back(make_pair(B[i], T[i]));
adj[B[i]].push_back(make_pair(A[i], T[i]));
edges[make_pair(A[i], B[i])] = T[i];
edges[make_pair(B[i], A[i])] = T[i];
}
int cur = 0;
for (int i = 0; i < N; i++)
{
ccnum[i] = -1;
}
for (int i = 0; i < N; i++)
{
if (ccnum[i] == -1)
{
queue <int> curs;
curs.push(i);
ccnum[i] = cur;
while (!curs.empty())
{
int a = curs.front();
curs.pop();
for (auto x : adj[a])
{
if (ccnum[x.first] == -1)
{
ccnum[x.first] = cur;
curs.push(x.first);
}
}
}
cur++;
}
}
for (int i = 0; i < N; i++)
{
cc[ccnum[i]].push_back(i);
layer[i] = -1;
}
maxgrp = cur - 1;
for (int i = 0; i <= maxgrp; i++)
{
if (cc[i].size() == 1)
{
if (m3 < 0)
{
m3 = 0;
if (m3 > m2)
{
swap(m3, m2);
if (m2 > m1)
{
swap(m2, m1);
}
}
}
continue;
}
bool path = true;
roots[i] = cc[i][0];
queue <pii> depth;
layer[roots[i]] = 0;
depth.push(make_pair(roots[i], 0));
map <int, vector <int>> layers;
layers[0].push_back(roots[i]);
int maxlayer = 0;
map <int, vector <int>> children;
map <int, int> parent;
map <int, pii> big;
for (int a : cc[i])
{
parent[a] = -1;
}
while (!depth.empty())
{
pii a = depth.front();
depth.pop();
for (pii b : adj[a.first])
{
if (layer[b.first] == -1)
{
depth.push(make_pair(b.first, a.second + 1));
layer[b.first] = a.second + 1;
layers[a.second + 1].push_back(b.first);
maxlayer = max(maxlayer, a.second + 1);
children[a.first].push_back(b.first);
if (children[a.first].size() >= 2)
{
path = false;
}
parent[b.first] = a.first;
}
}
}
queue <int> calc;
map <int, bool> seen;
seen[-1] = true;
map <int, int> cseen;
for (int a : cc[i])
{
if (children[a].size() == 0)
{
calc.push(a);
seen[a] = true;
}
}
while (!calc.empty())
{
int a = calc.front();
calc.pop();
if (!seen[parent[a]])
{
cseen[parent[a]]++;
if (cseen[parent[a]] == children[parent[a]].size())
{
calc.push(parent[a]);
seen[parent[a]] = true;
}
}
if (children[a].size() == 0)
{
big[a] = make_pair(0, a);
continue;
}
pii x = make_pair(-1, -1);
for (int b : children[a])
{
int l1 = big[b].first;
if (l1 >= 0 && l1 + edges[make_pair(a, b)] > x.first)
{
x.first = l1 + edges[make_pair(a, b)];
x.second = big[b].second;
}
}
big[a] = x;
}
int start = -1;
int end = -1;
int common = -1;
ll length = 0;
ll tot = 0;
if (path)
{
start = roots[i];
int a = roots[i];
while (children[a].size() > 0)
{
length += edges[make_pair(a, children[a][0])];
a = children[a][0];
}
end = a;
}
else
{
for (int a : cc[i])
{
pii max1 = make_pair(0, 0);
pii max2 = make_pair(0, 0);
if (children[a].size() >= 2)
{
for (int b : children[a])
{
if (edges[make_pair(a, b)] + big[b].first > max2.first)
{
max2 = make_pair(edges[make_pair(a, b)] + big[b].first, big[b].second);
if (max2 > max1)
{
swap(max2, max1);
}
}
}
if (max1.first + max2.first > length)
{
length = max1.first + max2.first;
start = max1.second;
end = max2.second;
common = a;
path = false;
}
}
else if (children[a].size() == 1)
{
if (big[a].first > length)
{
length = big[a].first;
start = a;
end = big[a].second;
common = a;
path = true;
}
}
}
}
if (length > maxlen)
{
maxlen = length;
}
int curpos;
if (path)
{
curpos = end;
}
else
{
curpos = start;
}
int minmax = 0;
while (tot * 2 < length)
{
tot += edges[make_pair(curpos, parent[curpos])];
if (tot * 2 == length)
{
minmax = tot;
}
if (tot * 2 > length)
{
if (tot * 2 - edges[make_pair(curpos, parent[curpos])] >= length)
{
minmax = length - tot + edges[make_pair(curpos, parent[curpos])];
}
else
{
minmax = tot;
}
}
curpos = parent[curpos];
}
if (m3 < minmax)
{
m3 = minmax;
if (m3 > m2)
{
swap(m3, m2);
if (m2 > m1)
{
swap(m2, m1);
}
}
}
cout << start << " " << end << " " << length << endl;
}
if (m2 == -1)
{
cout << max(maxlen, m1) << endl;
}
else if (m3 == -1)
{
cout << max(maxlen, m1 + L + m2) << endl;
}
else
{
cout << max(maxlen, max(m1 + L + m2, m2 + m3 + 2 * L)) << endl;
}
}