Submission #1193142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193142		mannshah1211	Factories (JOI14_factories)	C++17	100 / 100	2591 ms	321764 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<pair<int, int>>> g;
vector<int> sub;
vector<bool> alive;
vector<vector<pair<int, long long>>> ancs;
vector<long long> mn;

const long long inf = (long long) 1e18;

int dfs(int v, int pr) {
  sub[v] = 1;
  for (auto [u, w] : g[v]) {
    if (u != pr && alive[u]) {
      sub[v] += dfs(u, v);
    }
  }
  return sub[v];
}

int find(int v, int pr, int sz) {
  for (auto [u, w] : g[v]) {
    if (u != pr && alive[u] && 2 * sub[u] > sz) {
      return find(u, v, sz);
    }
  }
  return v;
}

void distance(int v, int pr, int centroid, long long cur) {
  for (auto [u, w] : g[v]) {
    if (u != pr && alive[u]) {
      distance(u, v, centroid, cur + w);
    }
  }
  ancs[v].push_back(make_pair(centroid, cur));
}

void build(int v) {
  int centroid = find(v, -1, dfs(v, -1));
  for (auto [u, w] : g[centroid]) {
    if (alive[u]) {
      distance(u, centroid, centroid, w);
    }
  }
  alive[centroid] = false;
  for (auto [u, w] : g[centroid]) {
    if (alive[u]) {
      build(u);
    }
  }
}

vector<int> modified;

void paint(int v) {
  for (auto [anc, d] : ancs[v]) {
    mn[anc] = min(mn[anc], d);
    modified.push_back(anc);
  }
  mn[v] = 0;
  modified.push_back(v);
}

long long query(int v) {
  long long ans = mn[v];
  for (auto [anc, d] : ancs[v]) {
    ans = min(ans, mn[anc] + d);
  }
  return ans;
}

void reset() {
  for (int v : modified) {
    mn[v] = inf;
  }
  modified.clear();
}

void Init(int n, int a[], int b[], int d[]) {
  g.resize(n);
  for (int i = 0; i < n - 1; i++) {
    g[a[i]].emplace_back(b[i], d[i]);
    g[b[i]].emplace_back(a[i], d[i]);
  }
  sub.resize(n);
  alive.assign(n, true);
  ancs.resize(n);
  build(0);
  mn.assign(n, inf);
}

long long Query(int s, int x[], int t, int y[]) {
  for (int i = 0; i < s; i++) {
    paint(x[i]);
  }
  long long ans = inf;
  for (int i = 0; i < t; i++) {
    ans = min(ans, query(y[i]));
  }
  reset();
  return ans;
}

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