Submission #854446

#	Time	Username	Problem	Language	Result	Execution time	Memory
854446		gun_gan	Factories (JOI14_factories)	C++17	0 / 100	12 ms	45756 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MX = 5e5 + 5;
 
int N, Q;
 
ll sz[MX], ans[MX];
bool removed[MX];
 
vector<pair<int,int>> g[MX];
 
int getSize(int v, int p) {
      sz[v] = 1;
      for(auto [u, w] : g[v]) {
            if(u == p || removed[u]) continue; 
            sz[v] += getSize(u, v);
      }
      return sz[v];
}
 
int getCentroid(int v, int p, int size) {
      for(auto [u, w] : g[v]) {
            if(u != p && sz[u] > size / 2 && !removed[u]) {
                  return getCentroid(u, v, size);
            }
      }
 
      return v;
}
 
vector<pair<ll,ll>> ancestors[MX];
 
void getDists(int v, int centroid, int p, int curDist) {
      for(auto [u, w] : g[v]) {
            if(u == p || removed[u]) continue;
            getDists(u, centroid, v, curDist + w); 
      }
 
      ancestors[v].push_back({centroid, curDist});
}
 
void build(int v) {
      int centroid = getCentroid(v, -1, getSize(v, -1));
 
      for(auto [u, w] : g[centroid]) {
            if(removed[u]) continue;
            getDists(u, centroid, centroid, w);
      }
 
      removed[centroid] = 1;
 
      for(auto [u, w] : g[centroid]) {
            if(removed[u]) continue;
            build(u);
      }
}
 
void Init(int _N, int A[], int B[], int D[]) {
      N = _N;
      for(int i = 0; i < N - 1; i++) {
            g[A[i]].push_back({B[i], D[i]});
            g[B[i]].push_back({A[i], D[i]});
      }
 
      build(0);
      for(int i = 0; i < N; i++) ancestors[i].push_back({i, 0});
}
 
long long Query(int s, int X[], int t, int Y[]) {
      vector<int> R;
      for(int i = 0; i < s; i++) {
            int x = X[i];
 
            for(auto [y, d] : ancestors[x]) {
                  R.push_back(y);
                  ans[y] = min(ans[y], d);
            }
      }
 
      ll res = 1e18;
      for(int i = 0; i < t; i++) {
            int x = Y[i];
 
            for(auto [y, d] : ancestors[x]) {
                  res = min(res, d + ans[y]);
            }
      }
 
      for(auto x : R) ans[x] = 1e18;
 
      return res;
}

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