제출 #1318447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318447		Johan	꿈 (IOI13_dreaming)	C++20	47 / 100	1096 ms	35800 KiB

dreaming

#include "dreaming.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;
int pa[N];
vector < int > adj[N];
unordered_map < int , int > dist;
map < pair < int , int > , int > we;
vector < int > par(N, -1);
int find(int u){
  if(par[u] < 0)return u;
  else return par[u] = find(par[u]);
}
void uni(int u, int v){
  u = find(u);
  v = find(v);
  if(u == v)return;
  par[u] += par[v];
  par[v] = u;
}
void dfs(int u, int p = -1){
  for(auto v : adj[u]){
    if(v != p){
      dist[v] = dist[u] + we[{u, v}];
      dfs(v, u);
    }
  }
}
void dfs_(int u, int end, int p = -1){
  pa[u] = p;
  for(auto v : adj[u]){
    if(v != p)
      dfs_(v, end, u);
  }
}
pair < int , int > centre(int st, int end){
  int sz = 0;
  vector < int > path = {end};
  while(end != st){
    sz += we[{end, pa[end]}];
    end = pa[end];
    path.push_back(end);    
  }
  int mn = sz, diametr = sz, cur = 0, node = path[0], far;
  for(int i = 1; i < path.size(); i++){
    int W = we[{path[i], path[i - 1]}];
    sz -= W;
    cur += W;
    if(mn > max(sz, cur)){
      if(sz > cur)far = path.back();
      else far = path[0];
      mn = max(sz, cur);
      node = path[i];
    }
  }
  return {diametr, node};
}
pair < int , int > find_diametr(int Node){
	dfs(Node);
  int mx = 0, u = Node, v = Node;
  for(auto e : dist){
    int node = e.first;
    int dis = e.second;
    if(dis > mx){
      mx = dis;
      u = node;
    }
  }
  mx = 0;
  dist.clear();
  dfs(u);
  for(auto e : dist){
    int node = e.first;
    int dis = e.second;
    if(dis > mx){
      mx = dis;
      v = node;
    }
  }
  dist.clear();
  dfs_(u, v);
  return {u, v};
}
int travelTime(int n, int m, int L, int u[], int v[], int w[]){
  for(int i = 0; i < m; i++){
    we[{u[i], v[i]}] = w[i];
    we[{v[i], u[i]}] = w[i];
    adj[u[i]].push_back(v[i]);
    adj[v[i]].push_back(u[i]);  
    uni(u[i], v[i]);
  }
  set < int > cmps;
  for(int i = 0; i < n; i++)
    cmps.insert(find(i));
  vector < pair < int , int > > x;
  for(auto nd : cmps){
    pair < int , int > p = find_diametr(nd);
    int u = p.first;
    int v = p.second;
    x.push_back(centre(u, v));
  }
  sort(x.rbegin(), x.rend());
  int Node = x[0].second;
  for(int i = x.size() - 1; i >= 1; i--){
    adj[Node].push_back(x[i].second);
    adj[x[i].second].push_back(Node);
    we[{Node, x[i].second}] = L;
    we[{x[i].second, Node}] = L;
    pair < int , int > p = find_diametr(Node);
    int U = p.first;
    int V = p.second;
    pair < int , int > q = centre(U, V);
    Node = q.second;
    x[0].first = q.first; 
  }
  return x[0].first;
}
// #define MAX_N 100000

// static int A[MAX_N];
// static int B[MAX_N];
// static int T[MAX_N];

// int main() {
// 	int N, M, L, i;
// 	int res;

// // 	FILE *f = fopen("dreaming.in", "r");
// // 	if (!f)
// 		// fail("Failed to open input file.");

// 	res = scanf("%d%d%d", &N, &M, &L);
// 	for (i = 0; i < M; i++)
// 		res = scanf("%d%d%d", &A[i], &B[i], &T[i]);
// // 	fclose(f);

// 	int answer = travelTime(N, M, L, A, B, T);
// 	printf("%d\n", answer);

// 	return 0;
// }
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/

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