Submission #400406

#	Time	Username	Problem	Language	Result	Execution time	Memory
400406		Haunted_Cpp	Factories (JOI14_factories)	C++17	100 / 100	5440 ms	333836 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long i64;
 
const int MAX_N = 500000 + 5;
 
const i64 INF = 1e18;
 
vector<pair<int, int>> g[MAX_N];
vector<pair<int, i64>> par[MAX_N];
 
int sub[MAX_N], del[MAX_N];
i64 best_way[MAX_N];
 
int calc_subtree(int node, int p) {
  sub[node] = 1;
  for (auto to : g[node]) {
    if (to.first != p && !del[to.first]) {
      sub[node] += calc_subtree(to.first, node);
    }
  }
  return sub[node];
}
 
int calc_centroid(int node, int p, const int tam) {
  for (auto to : g[node]) {
    if (!del[to.first] && to.first != p && sub[to.first] > tam / 2) {
      return calc_centroid(to.first, node, tam);
    }
  }
  return node;
}
 
void solve(int node, int p, const int centroid, i64 w) {
  par[node].emplace_back(centroid, w);
  for (auto to : g[node]) {
    if (!del[to.first] && to.first != p) {
      solve(to.first, node, centroid, w + to.second);
    }
  }
}
 
void decompose(int node) {
  const int centroid = calc_centroid(node, -1, calc_subtree(node, -1));
  del[centroid] = 1;
  for (auto to : g[centroid]) {
    if (!del[to.first]) {
      solve(to.first, -1, centroid, to.second);
      decompose(to.first);
    }
  }
} 
 
void Init(int N, int A[], int B[], int D[]) {
  for (int i = 0; i < N - 1; i++) {
    const int st = A[i];
    const int et = B[i];
    const int w = D[i];
    g[st].emplace_back(et, w);
    g[et].emplace_back(st, w);
  }
  decompose(0);
  for (int i = 0; i < MAX_N; i++) {
    best_way[i] = INF;
  }
}
 
i64 Query(int S, int X[], int T, int Y[]) {
  i64 mn = INF;
  for (int i = 0; i < S; i++) {
    best_way[X[i]] = 0;
    for (auto to : par[X[i]]) {
      best_way[to.first] = min(best_way[to.first], to.second);
    }
  }
  for (int i = 0; i < T; i++) {
    mn = min(mn, best_way[Y[i]]);
    for (auto to : par[Y[i]]) {
      mn = min(mn, best_way[to.first] + to.second);
    }
  }
  for (int i = 0; i < S; i++) {
    best_way[X[i]] = INF;
    for (auto to : par[X[i]]) {
      best_way[to.first] = INF;
    }
  }
  return mn;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67