Submission #1256667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256667		julia_08	Factories (JOI14_factories)	C++20	0 / 100	2259 ms	291472 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];

multiset<int> ms[MAXN];

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]){
    if(x == 1){
      ms[c].insert(d);
    } else ms[c].erase(ms[c].find(d));
  }

}

ll query(int v){

  ll r = INF;

  for(auto [c, d] : ancestors[v]){
    if(!ms[c].empty()){
      r = min(r, d + *ms[c].begin());
    }
  }

  return r;

}

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

  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], 1);

  ll ans = INF;

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

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

  return ans;

}

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