Submission #993806

#	Time	Username	Problem	Language	Result	Execution time	Memory
993806		UVince	Factories (JOI14_factories)	C++17	0 / 100	26 ms	62040 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using ll=long long;
using namespace std;

const int maxn = 5e5+1;
vector<vector<pair<int,ll>>> g(maxn);
vector<int> parent(maxn);
vector<int> subsize(maxn);
vector<bool> isremoved(maxn,false);
vector<map<int, ll>> d(maxn);
vector<ll> far(maxn, INT_MAX);
vector<int> valid(maxn, 0);


int getsize(int v, int par=-1){
  subsize[v]=1;
  for (auto [to, dist] : g[v]){
    if (to == par || isremoved[to]) continue;
    subsize[v]+=getsize(to, v);
  }
  return subsize[v];
}

int getc(int v, int ts, int par=-1){
  for (auto [to, dist] : g[v]){
    if (to==par || isremoved[to]) continue;
    if (subsize[to]*2>ts) return getc(to,ts,v);
  }
  return v;
}

void calcdist(int v, int c, int par=-1){
  for (auto [to, dist] : g[v]){
    if (to==par || isremoved[to]) continue;
    d[c][to]=d[c][v]+dist;
    calcdist(to,c,v);
  }
}

void build(int v, int par){

  int c = getc(v, getsize(v));
  parent[c]=par;

  isremoved[c]=true;
  for (auto [to, dist] : g[c]){
    if (isremoved[to]) continue;
    d[c][to]=dist;
    calcdist(to, c, c);
    build(to, c);
  }
}

void Init(int N, int A[], int B[], int D[]) {
  for (int i=0;i<N-1;i++){
    g[A[i]+1].push_back({B[i]+1,D[i]});
    g[B[i]+1].push_back({A[i]+1, D[i]});
  }
  build(1, -1);

}

int id=0;

long long Query(int S, int X[], int T, int Y[]) {
  //y->x
  id++;
  for (int i=0;i<S;i++){
    int cur = X[i]+1;
    far[cur]=0;
    valid[cur]=id;
    auto p = parent[cur];
    while (p!=-1){
      if (valid[p]==id){
        if (far[cur]+d[p][cur]<far[p]){
          far[p]=far[cur]+d[p][cur];
        }
      }
      else {
        far[p]=far[cur]+d[p][cur];
        valid[p]=id;
      }
      p=parent[p];
    }
  }
  ll ans=1e11;
  for (int i=0;i<T;i++){
    int cur = Y[i]+1;
    auto p = parent[cur];
    while (p!=-1){
      if (valid[p]==id) ans=min(ans, far[p]+d[p][cur]);
      p=parent[p];
    }
  }
  return ans;
}

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