제출 #843414

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
843414		huutuan	공장들 (JOI14_factories)	C++17	100 / 100	2188 ms	296248 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vii vector<pii>
#define isz(x) (int)x.size()
using namespace std;
 
const int mxN = 1e6 + 10;
const ll oo = 1e18;
 
int n;
vector<vii> G;
 
vi vtn;
vector<vector<pair<ll, ll>>> vt;
 
ll dis[mxN];
pii sparse[20][mxN];
int timer, ecnt, ap[mxN], dep[mxN], cur[mxN], tin[mxN], tout[mxN];
 
void dfs(int v, int p)
{
   tin[v] = ++timer;
      if (p == -1){
      dep[v] = dis[v] = 0;
   }else dep[v] = dep[p] + 1;
   sparse[0][++ecnt] = {dep[v], v};
   ap[v] = ecnt;

   for (auto &[u, w] : G[v])
   {
      if (u == p)
         continue;
      dis[u] = dis[v] + w;
      dfs(u, v);
      sparse[0][++ecnt] = {dep[v], v};
   }

   tout[v] = ++timer;
}
 
void build_sparse()
{
   for (int p = 1, i = 1; p << 1 <= ecnt; p <<= 1, ++i)
      for (int j = 1; j <= ecnt - (p << 1) + 1; ++j)
         sparse[i][j] = min(sparse[i - 1][j], sparse[i - 1][j + p]);
}
 
bool is_ancestor(int u, int v)
{
   return tin[u] <= tin[v] && tout[u] >= tout[v];
}
 
int LCA(int u, int v)
{
   int l = ap[u], r = ap[v];
   if (l > r)
      swap(l, r);
   int len = r - l + 1, lg_len = __lg(len);
   return min(sparse[lg_len][l], sparse[lg_len][r - (1 << lg_len) + 1]).ss;
}
 
void Init(int N, int A[], int B[], int D[])
{
   n = N;
   G.resize(n);
   vt.resize(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]);
   }
   dfs(0, -1);
   build_sparse();
}
 
long long Query(int S, int X[], int T, int Y[])
{
   // queue<pii> q;
 
   for (int i = 0; i < S; ++i)
   {
      cur[X[i]] = 1;
      // q.emplace(X[i], 0);
      vtn.emplace_back(X[i]);
   }
   for (int i = 0; i < T; ++i)
   {
      cur[Y[i]] = 2;
      vtn.emplace_back(Y[i]);
   }
 
   sort(all(vtn), [&](int u, int v)
        { return tin[u] < tin[v]; });
 
   for (int i = 0; i < S + T - 1; ++i)
   {
      vtn.emplace_back(LCA(vtn[i], vtn[i + 1]));
   }
 
   sort(all(vtn), [&](int u, int v)
        { return tin[u] < tin[v]; });
   vtn.erase(unique(all(vtn)), vtn.end());
 
   auto add_vt = [&](int u, int v, ll w)
   {
      vt[u].emplace_back(v, w);
      vt[v].emplace_back(u, w);
   };
 
   stack<int> s;
   for (int i = 0; i < isz(vtn); ++i)
   {
      while (not s.empty() && not is_ancestor(s.top(), vtn[i]))
         s.pop();
      if (s.empty())
         s.emplace(vtn[i]);
      else
      {
         add_vt(s.top(), vtn[i], dis[vtn[i]] - dis[s.top()]);
         s.emplace(vtn[i]);
      }
   }
 
   ll res = oo;
 
   auto dfs = [&](auto self, int v, int p) -> vll
   {
      vll cur_dis(2, oo);
      if (cur[v])
         cur_dis[cur[v] - 1] = 0;
      for (auto &[u, w] : vt[v])
      {
         if (u == p)
            continue;
         vll tmp = self(self, u, v);
         for (int i = 0; i < 2; ++i)
            cur_dis[i] = min(cur_dis[i], tmp[i] + w);
      }
      res = min(res, accumulate(all(cur_dis), 0LL));
      return cur_dis;
   };
 
   dfs(dfs, vtn[0], -1);
 
   // for (int i = 0; i < S; ++i)
   // {
   //    cur[X[i]] = 0;
   //    // vt[X[i]].clear();
   // }
   // for (int i = 0; i < T; ++i)
   // {
   //    cur[Y[i]] = 0;
   //    // vt[Y[i]].clear();
   // }
   for (int i:vtn) vt[i].clear(), cur[i] = 0;
   vtn.clear();

   return res;
}

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