| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 482212 | M_W | 꿈 (IOI13_dreaming) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "dreaming.h"
#define ii pair<int, int>
using namespace std;
vector<ii> adj[100001];
int pa[100001], from[100001], dist[100001];
bitset<100001> mark, mark2;
int findpa(int a){
return (pa[a] == a ? a : pa[a] = findpa(pa[a]));
}
ii longestDist(int st){
queue<ii> q;
ii best = make_pair(-1, 0);
q.push(make_pair(0, st));
mark[st] = 1;
while(!q.empty()){
int d = q.front().first;
int n = q.front().second;
q.pop();
if(d > best.first){
best = make_pair(d, n);
}
for(auto x : adj[n]){
if(!mark[x.first]){
mark[x.first] = 1;
q.push(make_pair(d + x.second, x.first));
}
}
}
q.push(make_pair(0, best.second));
mark2[best.second] = 1;
best = make_pair(-1, 0);
while(!q.empty()){
int d = q.front().first;
int n = q.front().second;
q.pop();
dist[n] = d;
if(d > best.first){
best = make_pair(d, n);
}
for(auto x : adj[n]){
if(!mark2[x.first]){
from[x.first] = n;
mark2[x.first] = 1;
q.push(make_pair(d + x.second, x.first));
}
}
}
int mid = 0;
for(int i = best.second; i != 0; i = from[i]){
if(abs(best.first - mid - mid) > abs(best.first - dist[i] - dist[i])){
mid = dist[i];
}
}
return make_pair(best.first, max(best.first - mid, mid));
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
for(int i = 1; i <= N; i++) pa[i] = i;
for(int i = 0; i < M; i++){
A[i]++;
B[i]++;
adj[A[i]].emplace_back(B[i], T[i]);
adj[B[i]].emplace_back(A[i], T[i]);
if(findpa(A[i]) != findpa(B[i])){
pa[findpa(B[i])] = findpa(A[i]);
}
}
for(int i = 1; i <= N; i++){
for(auto x : adj[i]){
}
}
priority_queue<ii> pq;
for(int i = 1; i <= N; i++){
if(pa[i] == i){
ii tmp = longestDist(i);
pq.push(tmp);
}
}
if(pq.size() == 1) return 0;
int cnt = 2, ans = 0;
while(cnt--){
ans += pq.top().second;
pq.pop();
}
return ans + L;
}
int main(){
// int a[8] = {0, 8, 2, 5, 5, 1, 1, 10}, b[8] = {8,2,7,11,1,3,9,6}, c[8] = {4,2,4,3,7,1,5,3};
// printf("%d", travelTime(12, 8, 2, a, b, c));
}