Submission #29231

#	Time	Username	Problem	Language	Result	Execution time	Memory
29231		ruhanhabib39	Factories (JOI14_factories)	C++14	100 / 100	4976 ms	212464 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;

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

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

void dfs(int u, int p, long long ds) {
   dis[u][++level[u]] = ds;
   cc[u] = 1;
   for(auto e : G[u]) {
      int v, d; tie(v, d) = e;
      if(v == p || done[v]) continue;
      dfs(v, u, ds + d);
      cc[u] += cc[v];
   }
}

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

void decomp(int u, int p) {
   u = centroid(u, -1, cc[u]); dfs(u, -1, 0);
   // cerr << "centroid = " << u << "\n";
   par[u] = p;
   done[u] = true;
   for(auto e : G[u]) {
      int v = e.first;
      if(done[v]) continue;
      decomp(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]].emplace_back(B[i], D[i]);
      G[B[i]].emplace_back(A[i], D[i]);
   }
   memset(level, -1, sizeof(level));
   dfs(0, -1, 0);
   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[X[i]][j]);
         // 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[Y[i]][j]);
         u = par[u];
      }
   }
   for(int i = 0; i < S; i++) {
      int u = X[i];
      for(int j = level[u]; j > 0; j--) {
         mn[u] = INF;
         u = par[u];
      }
   }
   return res;
}

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