Submission #1256677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256677		julia_08	Factories (JOI14_factories)	C++20	100 / 100	3014 ms	355588 KiB

factories

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

using namespace std;

using ll = long long;

const int MAXN = 5e5 + 10;
const ll INF = 1e18;

int used[MAXN], sub[MAXN]; 

ll dist[MAXN];

vector<pair<int, ll>> adj[MAXN], ancestors[MAXN];

pair<ll, ll> min_dist[MAXN];

int q = 0;

int get_size(int v, int p){

  sub[v] = 1;

  for(auto [u, w] : adj[v]){
    if(used[u] || u == p) continue;
    sub[v] += get_size(u, v);
  }

  return sub[v];

}

int get_centroid(int v, int p, int sz){

  for(auto [u, w] : adj[v]){
    if(used[u] || u == p) continue;
    if(sub[u] > sz / 2) return get_centroid(u, v, sz);
  }

  return v;

}

void get_dists(int v, int p, int c){

  for(auto [u, w] : adj[v]){
    if(used[u] || u == p) continue;
    dist[u] = dist[v] + w;
    get_dists(u, v, c);
  }

  ancestors[v].push_back({c, dist[v]});

}

void build(int v, int p){

  int c = get_centroid(v, p, get_size(v, p));

  used[c] = 1;
  dist[c] = 0;

  get_dists(c, c, c);

  for(auto [u, w] : adj[c]){
    if(used[u]) continue;
    build(u, c);
  }

}

void paint(int v, int x){

  for(auto [c, d] : ancestors[v]){
    min_dist[c] = min(min_dist[c], {-x, d});
  }

}

ll query(int v){

  pair<ll, ll> r = {INF, INF};

  for(auto [c, d] : ancestors[v]){
    r = min(r, {min_dist[c].first, d + min_dist[c].second});
  }

  return r.second;

}

void Init(int n, int a[], int b[], int d[]){

  for(int i=0; i<n; i++) min_dist[i] = {INF, INF};

  for(int i=0; i<(n - 1); i++){
    adj[a[i]].push_back({b[i], d[i]});
    adj[b[i]].push_back({a[i], d[i]});
  }

  build(0, 0);

}

ll Query(int s, int x[], int t, int y[]){

  for(int i=0; i<s; i++) paint(x[i], q);

  q ++;

  ll ans = INF;

  for(int i=0; i<t; i++) ans = min(ans, query(y[i]));

  return ans;

}

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