| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 482219 | M_W | 꿈 (IOI13_dreaming) | C++14 | 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"
#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 = INT_MAX;
for(int i = best.second; i != 0; i = from[i]){
mid = min(mid, max(best.first - dist[i], dist[i]));
}
return make_pair(best.first, 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]);
}
}
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;
int aaa = pq.top().first;
while(cnt--){
ans += pq.top().second;
pq.pop();
}
return max(aaa, ans + L, 2 * L);
}
/*
int main(){
int N, M, L;
scanf("%d %d %d", &N, &M, &L);
int a[M], b[M], c[M];
for(int i = 0; i < M; i++){
scanf("%d %d %d", &a[i], &b[i], &c[i]);
}
printf("%d", travelTime(N, M, L, a, b, c));
}
*/