제출 #1149411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149411		epicci23	Dreaming (IOI13_dreaming)	C++20	100 / 100	145 ms	13968 KiB

dreaming

#include "bits/stdc++.h"
#include "dreaming.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 1e5 + 5;
const int INF = 2e9;
vector<array<int,2>> v[N];
int vis[N],dist[N], ans = 0, best = -1;
array<int,2> di[2];

void dfs(int c,int p,int d,int rt){
  di[rt] = max(di[rt], array<int,2>{d, c});
  for(auto [u, w] : v[c]){
    if(u == p) continue;
    dfs(u,c,w+d,rt);
  }
}

void calc(int c,int p,int d){
  dist[c] = max(dist[c], d);
  for(auto [u,w] : v[c]){
    if(u == p) continue;
    calc(u,c,d + w);
  }
}

void mark(int c){
  if(vis[c]) return;
  if(best == -1) best = dist[c];
  else best = min(best, dist[c]);
  vis[c] = 1;
  for(auto [u,w] : v[c]) mark(u);
}

int travelTime(int _n, int _m, int L, int A[], int B[], int T[]) {
  int n = _n, m = _m;
  for(int i=0;i<m;i++){
  	int a = A[i],b = B[i],c = T[i];
  	v[a].push_back({b,c});
  	v[b].push_back({a,c});
  }
  
  vector<int> ar;
  
  for(int i=0;i<n;i++){
    if(vis[i]) continue;
    di[0] = di[1] = {0, 0};
    dfs(i,i,0,0);
    dfs(di[0][1],di[0][1],0,1);
    calc(di[0][1],di[0][1],0);
    calc(di[1][1],di[1][1],0);
    ans=max(ans,di[1][0]);
    best = -1;
    mark(i);
    ar.push_back(best);
  }

  sort(all(ar));
  if(sz(ar) == 1) return ans;
  
  if(sz(ar) == 2){
  	ans=max(ans, ar[0] + ar[1] + L);
  	return ans;
  }

  int xd = sz(ar) - 1;
  ans=max(ans, ar[xd] + ar[xd - 1] + L);
  ans=max(ans, ar[xd-1] + ar[xd-2] + 2 * L);

  return ans;
}


/*void _(){
	
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23