Submission #1142332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142332		DaciejMaciej	Factories (JOI14_factories)	C++20	100 / 100	2502 ms	345940 KiB

factories

#include "factories.h"

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ld;

template <class T>

using VV = vector<vector<T>>;

using VI = vector<int>;
using VVI = vector<vector<int>>;

using VL = vector<long long>;
using VVL = vector<vector<long long>>;

using VC = vector<char>;
using VVC = vector<vector<char>>;

using VB = vector<bool>;
using VVB = vector<vector<bool>>;

using VD = vector<double>;
using VVD = vector<vector<double>>;

using PII = pair<int, int>;
using PLL = pair<long long, long long>;
using PIL = pair<int, long long>;
using PLI = pair<long long, int>;

using VPII = vector<pair<int, int>>;
using VPLL = vector<pair<long long, long long>>;

#define LINE '\n'
#define SPACE ' '
#define PB push_back
#define FOR(i, a, b) for (int i = (a); i < (int(b)); i++)
#define FORE(i, a, b) for (int i = (a); i <= (int)((b)); i++)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define sq(a) ((a) * (a))
#define sz(x) ((int)x.size())

#define fastio()                    \
  ios_base::sync_with_stdio(false); \
  cin.tie(nullptr);                 \
  cout.tie(nullptr)
#define debug(x) cerr << #x << " = " << x << endl;

const ll MOD = 1e9 + 7;

template <class T>
inline void mini(T &a, T b)
{
  a = min(a, b);
}

const int INF = 1e9;

const int MAX_N = 1e6 + 3;

bool off[MAX_N];
int sz[MAX_N];
VPII g[MAX_N];
VL dp(MAX_N, LLONG_MAX/3);
vector<pair<int, ll>> anc[MAX_N];

int find_centroid(int c, int p, int tsz)
{
  for (auto [v, _] : g[c])
  {
    if (v == p || off[v])
      continue;
    if (2 * sz[v] > tsz)
      return find_centroid(v, c, tsz);
  }
  return c;
}

// dist to centroid ancestors
void calc_dists(int c, int p, int centroid, ll dist)
{
  for (auto [v, edge] : g[c])
  {
    if (v == p || off[v])
      continue;
    calc_dists(v, c, centroid, dist + (ll)edge);
  }
  anc[c].PB({centroid, dist});
}

int calc_size(int c, int p)
{
  sz[c] = 1;
  for (auto [v, _] : g[c])
  {
    if (v == p || off[v])
      continue;
    sz[c] += calc_size(v, c);
  }
  return sz[c];
}

void decompose(int node)
{
  int cent = find_centroid(node, -1, calc_size(node, -1));

  for (auto [v, edge] : g[cent])
  {
    if (off[v])
      continue;
    calc_dists(v, cent, cent, edge);
  }

  off[cent] = true;
  for (auto [v, _] : g[cent])
  {
    if (off[v])
      continue;
    decompose(v);
  }
}

void update(int v, bool rem = false)
{
  if (rem)
  {
    dp[v] = LLONG_MAX/3;
    for (auto &[upnode, dist] : anc[v])
    {
      dp[upnode] = LLONG_MAX/3;
    }
    return;
  }

  dp[v] = 0;
  for (auto &[upnode, dist] : anc[v])
  {
    mini(dp[upnode], dist);
  }
}

ll query(int v)
{
  ll ret = dp[v];
  for (auto &[upnode, dist] : anc[v])
  {
    mini(ret, dp[upnode] + dist);
  }

  return ret;
}

void Init(int n, int A[], int B[], int D[])
{
  FOR(i, 0, n - 1)
  {
    int a = A[i];
    int b = B[i];
    int d = D[i];
    g[a].PB({b, d});
    g[b].PB({a, d});
  }

  decompose(0);
}

long long Query(int S, int X[], int T, int Y[])
{
  FOR(i, 0, S)
  {
    update(X[i]);
  }

  ll ans = LLONG_MAX/3;
  FOR(i, 0, T)
  {
    mini(ans, query(Y[i]));
  }

  FOR(i, 0, S)
  {
    update(X[i], true);
  }

  return ans;
}

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