| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 335966 | blue | Dreaming (IOI13_dreaming) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "dreaming.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;
/*
0 --(1)-- 1
|
(4)
|
4 --(3)-- 5
|
(4)
|
2 --(2)-- 3
Let the root of a connected component be the vertex whose maximum distance from any other vertex in the
connected component is minimum.
All additional edges must be built with both endpoints as roots.
Only one root has more than one additional edge - that with the highest
*/
//complete redo
vector<int> edge[100001];
vector<int> weight[100001];
vector<int> edge_size(1e5 + 1, 0);
vector<int> maxdist(1e5 + 1, 0);
vector<int> visit(1e5 + 1, 0);
vector<int> roots;
struct distcomp
{
int i;
};
bool operator < (distcomp A, distcomp B)
{
if(maxdist[A.i] == maxdist[B.i]) return A.i < B.i;
return maxdist[A.i] < maxdist[B.i];
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for(int i = 0; i < M; i++)
{
edge[A[i]].push_back(B[i]);
weight[A[i]].push_back(T[i]);
edge_size[A[i]]++;
edge[B[i]].push_back(A[i]);
weight[B[i]].push_back(T[i]);
edge_size[B[i]]++;
}
set<distcomp> tbv;
for(int i = 0; i < N; i++)
{
if(edge_size[i] == 1) tbv.insert(distcomp{i});
}
int u, v, w;
int flag;
while(!tbv.empty())
{
u = tbv.begin()->i;
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]) continue;
edge_size[v]--;
maxdist[v] = max(maxdist[v], maxdist[u] + w);
flag = 0;
if(edge_size[v] == 1)
{
tbv.insert(distcomp{v});
}
}
}
for(int i = 0; i < N; i++) if(edge_size[i] == 0)
{
roots.push_back(i);
}
int res = 0;
int max1, max2;
for(int r: roots)
{
max1 = max2 = 0;
for(int i = 0; i < edge[r].size(); i++)
{
v = edge[r][i];
w = weight[r][i];
if(maxdist[v] + w >= max1)
{
max2 = max1;
max1 = maxdist[v] + w;
}
else if(maxdist[v] + w >= max2) max2 = maxdist[v] + w;
}
res = max(res, max1 + max2);
}
for(int i = 0; i < roots.size(); i++) roots[i] = -1 * maxdist[roots[i]];
sort(roots.begin(), roots.end());
if(roots.size() >= 2) res = max(res, L - roots[0] - roots[1]);
if(roots.size() >= 3) res = max(res, 2*L - roots[1] - roots[2]);
int res0 = res;
if(roots.size() >= 2) res0 = max(res0, L - roots[0] - roots[1]);
if(roots.size() >= 3) res0 = max(res0, 2*L - roots[1] - roots[2]);
int res1 = res;
if(roots.size() >= 2) res1 = max(res1, L - roots[0] - roots[2]);
if(roots.size() >= 3) res1 = max(res1, 2*L - roots[0] - roots[2]);
res = min(res, res1);
res = min(res, res2);
return res;
}