oj.uz

Submission #843414

# Submission time Handle Problem Language Result Execution time Memory
843414 2023-09-04T01:48:44 Z huutuan Factories (JOI14_factories) C++17
100 / 100
 2188 ms 296248 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47704 KB Output is correct
2 Correct 621 ms 62808 KB Output is correct
3 Correct 631 ms 62924 KB Output is correct
4 Correct 588 ms 62844 KB Output is correct
5 Correct 666 ms 63180 KB Output is correct
6 Correct 376 ms 62752 KB Output is correct
7 Correct 594 ms 62816 KB Output is correct
8 Correct 576 ms 62804 KB Output is correct
9 Correct 588 ms 63172 KB Output is correct
10 Correct 391 ms 62668 KB Output is correct
11 Correct 571 ms 62824 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47708 KB Output is correct
2 Correct 894 ms 258888 KB Output is correct
3 Correct 1102 ms 263744 KB Output is correct
4 Correct 835 ms 258032 KB Output is correct
5 Correct 968 ms 296248 KB Output is correct
6 Correct 1061 ms 264116 KB Output is correct
7 Correct 791 ms 115752 KB Output is correct
8 Correct 631 ms 114784 KB Output is correct
9 Correct 633 ms 120116 KB Output is correct
10 Correct 761 ms 116364 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47704 KB Output is correct
2 Correct 621 ms 62808 KB Output is correct
3 Correct 631 ms 62924 KB Output is correct
4 Correct 588 ms 62844 KB Output is correct
5 Correct 666 ms 63180 KB Output is correct
6 Correct 376 ms 62752 KB Output is correct
7 Correct 594 ms 62816 KB Output is correct
8 Correct 576 ms 62804 KB Output is correct
9 Correct 588 ms 63172 KB Output is correct
10 Correct 391 ms 62668 KB Output is correct
11 Correct 571 ms 62824 KB Output is correct
12 Correct 7 ms 47708 KB Output is correct
13 Correct 894 ms 258888 KB Output is correct
14 Correct 1102 ms 263744 KB Output is correct
15 Correct 835 ms 258032 KB Output is correct
16 Correct 968 ms 296248 KB Output is correct
17 Correct 1061 ms 264116 KB Output is correct
18 Correct 791 ms 115752 KB Output is correct
19 Correct 631 ms 114784 KB Output is correct
20 Correct 633 ms 120116 KB Output is correct
21 Correct 761 ms 116364 KB Output is correct
22 Correct 2118 ms 266640 KB Output is correct
23 Correct 1728 ms 266616 KB Output is correct
24 Correct 2188 ms 270888 KB Output is correct
25 Correct 2068 ms 272584 KB Output is correct
26 Correct 1761 ms 266048 KB Output is correct
27 Correct 1865 ms 292940 KB Output is correct
28 Correct 1377 ms 263364 KB Output is correct
29 Correct 1697 ms 264840 KB Output is correct
30 Correct 1575 ms 264164 KB Output is correct
31 Correct 1589 ms 264884 KB Output is correct
32 Correct 901 ms 123864 KB Output is correct
33 Correct 653 ms 116872 KB Output is correct
34 Correct 947 ms 115520 KB Output is correct
35 Correct 896 ms 115524 KB Output is correct
36 Correct 954 ms 116124 KB Output is correct
37 Correct 1027 ms 116428 KB Output is correct