제출 #29222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
29222		ruhanhabib39	공장들 (JOI14_factories)	C++14	15 / 100	6000 ms	205748 KiB

factories

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

const int MAXN = 5e5;
const int MAXLG = 20;
const long long INF = 1e18;

struct dat {
   int v, w;
};

int N;
vector<dat> G[MAXN + 10];

int cc[MAXN + 10];
int level[MAXN + 10];
long long dis[MAXLG + 10][MAXN + 10];
bool done[MAXN + 10];
int par[MAXN + 10];

void dfs0(int u, int p) {
   cc[u] = 1;
   for(auto e : G[u]) {
      if(e.v == p || done[e.v]) continue;
      dfs0(e.v, u);
      cc[u] += cc[e.v];
   }
}

void dfs(int u, int p, long long ds) {
   // cerr << u << " " << p << " " << ds << "\n";
   dis[++level[u]][u] = ds;
   // cerr << "dis[" << level[u] << "][" << u << "] = " << dis[level[u]][u] << "\n";
   for(auto e : G[u]) {
      if(e.v == p || done[e.v]) continue;
      dfs(e.v, u, ds + e.w);
   }
}

int cnt;

int centroid(int u, int p) {
   for(auto e : G[u]) {
      if(e.v == p || done[e.v]) continue;
      if(cc[e.v] > cnt/2) return centroid(e.v, u);
   }
   return u;
}

void decomp(int u, int p) {
   dfs0(u, -1); cnt = cc[u];
   u = centroid(u, -1); dfs(u, -1, 0);
   // cerr << "centroid = " << u << "\n";
   par[u] = p;
   done[u] = true;
   for(auto e : G[u]) {
      if(done[e.v]) continue;
      decomp(e.v, u);
   }
}

long long mn[MAXN + 10];

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(dat{B[i], D[i]});
      G[B[i]].push_back(dat{A[i], D[i]});
   }
   decomp(0, -1);
   std::fill(mn, mn + MAXN + 1, INF);
}

long long Query(int S, int X[], int T, int Y[]) {
   // cerr << "\n\n";
   for(int i = 0; i < S; i++) {
      int u = X[i];
      // cerr << "Xu = " << u << "\n";
      for(int j = level[u]; j > 0; j--) {
         mn[u] = min(mn[u], dis[j][X[i]]);
         // cerr << "mn[" << u << "] = " << mn[u] << "\n";
         u = par[u];
      }
   }
   long long res = INF;
   for(int i = 0; i < T; i++) {
      int u = Y[i];
      for(int j = level[u]; j > 0; j--) {
         res = min(res, mn[u] + dis[j][Y[i]]);
         u = par[u];
      }
   }
   for(int i = 0; i < S; i++) {
      int u = X[i];
      while(u != -1) {
         mn[u] = INF;
         u = par[u];
      }
   }
   return res;
}

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