| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 335197 | blue | 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 "dreaming.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;
vector<int> edge[100001];
vector<int> weight[100001];
vector<int> maxdist(100001, 0);
vector<int> children(100001, 0);
vector<int> visit(100001, 0);
vector<int> roots;
struct distcomp
{
bool operator () (int a, int b)
{
if(maxdist[a] == maxdist[b]) return a < b;
return maxdist[a] < maxdist[b];
}
};
int travelTime(int N, int M, int L, int A[], int B[], int T[])
//number of nodes, number of edges, common length, edge A[i]-A[i] with length T[i]
{
for(int i = 0; i < M; i++)
{
edge[A[i]].push_back(B[i]);
weight[A[i]].push_back(T[i]);
edge[B[i]].push_back(A[i]);
weight[B[i]].push_back(T[i]);
}
set<int, distcomp> tbv;
for(int i = 0; i < N; i++)
{
if(edge[i].size() == 0) roots.push_back(0);
if(edge[i].size() == 1) tbv.insert(i);
}
int u, v, w;
while(!tbv.empty())
{
u = *tbv.begin();
tbv.erase(tbv.begin());
visit[u] = 1;
for(int i = 0; i < edge[u].size(); i++)
{
v = edge[u][i];
w = weight[u][i];
if(!visit[v])
{
children[v]++;
maxdist[v] = max(maxdist[v], maxdist[u] + w);
if(children[v] == edge[v].size() - 1) tbv.insert(v);
}
else
{
maxdist[u] = max(maxdist[u], maxdist[v] + w);
}
}
if(edge[u].size() == children[u]) roots.push_back(maxdist[u]);
}
if(M == N-1) return roots[0];
else
{
sort(roots.begin(), roots.end());
return roots[roots.size() - 2] + L + roots[roots.size() - 1];
}
}