| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1312668 | kevin264 | Dreaming (IOI13_dreaming) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define sz(x) (int)(x.size())
#define ff first
#define ss second
#define m_p make_pair
#define INF INT_MAX
#define OO LLONG_MAX
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
using vvpii = vector<vector<pii > >;
template<typename T> using inverse_pq = priority_queue<T,vector<T>, greater<T> >;
template<typename T=int> void cin_vector(vector<T> &v) {for(int& i : v) cin>>i;}
pair<int,vi> djikstra(int n, int start, vector<vector<pii> >& g){
inverse_pq<pii> pq;
vi dist(n+1, INF);
pii ans={-1,-1};
pq.push({0,start});
dist[start]=0;
while(!pq.empty()){
int w=pq.top().ff,top=pq.top().ss; pq.pop();
if(w>dist[top]) continue;
if(ans.ss<w) ans={top,w};
for(auto i :g[top]){
int d=i.ss+w;
if(dist[i.ff]>d){
dist[i.ff]=d;
pq.push({d,i.ff});
}
}
}
return m_p(ans.ff,dist);
}
int take_center(int n, vector<vector<pii> >& g){
pair<int,vi> pr=djikstra(n,1,g);
int a=pr.ff;
pr=djikstra(n,a,g);
vi dista=pr.ss;
vi distb=djikstra(n,pr.ff,g).ss;
int center=-1;
for(int i=1;i<=n;i++){
// cout<<i<<": "<<dista[i]<<" "<<distb[i]<<' '<<max(dista[i],distb[i])<<endl;
center=center==-1 or max(dista[i],distb[i])<center ? max(dista[i],distb[i]) : center;
}
return center;
}
#undef int long long
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
int n=N;
int l=L;
vector<vector<pii> > g(n);
for(int i=0;i<M;i++){
g[A[i]].push_back({B[i],T[i]});
g[B[i]].push_back({A[i],T[i]});
}
vi centers;
unordered_map<int,int> mp;
int counter=1;
//encontra todas as arvores os centros de cada arvore
for(int i=0;i<n;i++){
if(mp.find(i)==mp.end()){
int sz=counter; counter++;
mp[i]=sz;
unordered_map<int,int> to_new;
queue<int> q;
q.push(i);
unordered_set<int> visited;
visited.insert(i);
to_new[i]=1;
vector<vector<pii> > current(2);
while(!q.empty()){
int top=q.front();q.pop();
for(auto j : g[top]){
if(visited.find(j.ff)==visited.end()){
visited.insert(j.ff);
mp[j.ff]=sz;
to_new[j.ff]=current.size();
q.push(j.ff);
vector<pii> empty;
current.push_back(empty);
current[to_new[top]].push_back({to_new[j.ff],j.ss});
current[to_new[j.ff]].push_back({to_new[top],j.ss});
}
}
}
/* cout<<i<<": "<<endl;
for(int i=1;i<current.size();i++){
cout<<i<<": ";
for(auto j : current[i]) cout<<j.ff<<" "<<j.ss<<" ";
cout<<endl;
}
cout<<"center: "<<take_center(current.size()-1,current);
cout<<endl<<endl;*/
centers.push_back(take_center(current.size()-1,current));
}
}
//for(auto center:centers) cout<<center<<' ';
//cout<<endl;
sort(centers.begin(),centers.end(), greater<int>());
if(centers.size()==1){
return centers[0];
}else if(centers.size()==2){
return centers[0]+centers[1]+l;
}else{
return max(centers[0]+centers[1]+l,centers[1]+centers[2]+2*l);
}
}