oj.uz

Submission #798920

# Submission time Handle Problem Language Result Execution time Memory
798920 2023-07-31T07:19:09 Z arush_agu Factories (JOI14_factories) C++17
100 / 100
 4525 ms 313004 KB 
#include "factories.h"
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#ifdef DEBUG
#include <time.h>
#endif

#define all(a) (a).begin(), (a).end()
#define rev(a) (a).rbegin(), (a).rend()
#define F first
#define S second
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x)                                                                 \
  {                                                                            \
    ++recur_depth;                                                             \
    auto x_ = x;                                                               \
    --recur_depth;                                                             \
    cerr << string(recur_depth, '\t') << "\e[91m" << __func__ << ":"           \
         << __LINE__ << "\t" << #x << " = " << x_ << "\e[39m" << endl;         \
  }
#else
#define dbg(x)
#endif

using namespace std;
using namespace __gnu_pbds;

typedef pair<int, int> ii;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> llll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vii;
typedef vector<vii> vvii;

typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll, ll>> vll;
typedef vector<vll> vvll;

typedef vector<bool> vb;

template <class type1>
using ordered_set = tree<type1, null_type, less<type1>, rb_tree_tag,
                         tree_order_statistics_node_update>;

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<
                                    !is_same<T_container, string>::value,
                                    typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v) {
  os << '{';
  string sep;
  for (const T &x : v)
    os << sep << x, sep = ", ";
  return os << '}';
}

const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 1e18;
const ld EPS = 1e-9;

const int MAXLG = 22;
const int MAX_EULER_N = 1e6 + 10;
const int MAXN = 5e5 + 10;

struct ST {
  int n;
  ii st[MAXLG][MAX_EULER_N];
  int lg2[MAX_EULER_N];

  void init(int n_, vii &a) {
    n = n_;
    for (int i = 0; i < n; i++)
      st[0][i] = a[i];

    for (int j = 1; j < MAXLG; j++)
      for (int i = 0; i + (1 << j) <= n; i++)
        st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);

    lg2[1] = 0;
    for (int i = 2; i < MAX_EULER_N; i++)
      lg2[i] = lg2[i / 2] + 1;
  }

  llll query(int l, int r) {
    if (l > r)
      swap(l, r);
    int k = lg2[r - l + 1];
    return min(st[k][l], st[k][r - (1 << k) + 1]);
  }
};

struct CD {
  int n;
  vll adj[MAXN];
  int sub_sz[MAXN];
  bool rm[MAXN];

  int cpar[MAXN];

  ll dist_0[MAXN];
  int depth[MAXN];
  vii euler;
  int first_occ[MAXN];

  ST st;

  ll val[MAXN];

  void init(int n_, vvll &a) {
    n = n_;
    for (int i = 0; i < n; i++)
      adj[i] = a[i];

    for (int i = 0; i < n; i++)
      sub_sz[i] = first_occ[i] = 0, rm[i] = 0, cpar[i] = depth[i] = -1,
      dist_0[i] = val[i] = INF;

    dfs(0);
    decompose();

    st.init(euler.size(), euler);
  }

  void dfs(int u, int p = -1, ll d = 0, int de = 0) {
    dist_0[u] = d;
    depth[u] = de;
    first_occ[u] = euler.size();
    euler.push_back({de, u});
    for (auto [v, w] : adj[u])
      if (v != p) {
        dfs(v, u, d + w, de + 1);
        euler.push_back({de, u});
      }
  }

  int lca(int u, int v) { return st.query(first_occ[u], first_occ[v]).second; }
  ll dist(int u, int v) {
    return dist_0[u] + dist_0[v] - 2 * dist_0[lca(u, v)];
  }

  int get_sub_sz(int u, int p = -1) {
    sub_sz[u] = 1;
    for (auto [v, _] : adj[u])
      if (v != p && !rm[v])
        sub_sz[u] += get_sub_sz(v, u);
    return sub_sz[u];
  }

  int get_centroid(int u, int ssz, int p = -1) {
    for (auto [v, _] : adj[u])
      if (v != p && !rm[v] && sub_sz[v] * 2 > ssz)
        return get_centroid(v, ssz, u);
    return u;
  }

  void decompose(int u = 0, int par = -1) {
    int c = get_centroid(u, get_sub_sz(u));
    rm[c] = 1;

    if (par != -1)
      cpar[c] = par;

    for (auto [v, _] : adj[c])
      if (!rm[v])
        decompose(v, c);
  }

  void upd(int u, bool flag) {
    for (int v = u; v != -1; v = cpar[v]) {
      if (!flag)
        val[v] = min(val[v], dist(u, v));
      else
        val[v] = INF;
    }
  }

  ll query(int u) {
    ll res = INF;
    for (int v = u; v != -1; v = cpar[v])
      res = min(res, val[v] + dist(u, v));
    return res;
  }
} cd;

void Init(int N, int A[], int B[], int D[]) {
  vvll adj(N);
  for (int i = 0; i < N - 1; i++)
    adj[A[i]].push_back({B[i], D[i]}), adj[B[i]].push_back({A[i], D[i]});

  cd.init(N, adj);
}

long long Query(int S, int X[], int T, int Y[]) {
  ll res = INF;
  for (int i = 0; i < S; i++)
    cd.upd(X[i], 0);
  for (int i = 0; i < T; i++)
    res = min(res, cd.query(Y[i]));
  for (int i = 0; i < S; i++)
    cd.upd(X[i], 1);
  return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 188632 KB Output is correct
2 Correct 422 ms 199504 KB Output is correct
3 Correct 506 ms 199176 KB Output is correct
4 Correct 500 ms 199112 KB Output is correct
5 Correct 481 ms 199320 KB Output is correct
6 Correct 259 ms 199000 KB Output is correct
7 Correct 489 ms 199068 KB Output is correct
8 Correct 481 ms 199112 KB Output is correct
9 Correct 526 ms 199420 KB Output is correct
10 Correct 259 ms 199056 KB Output is correct
11 Correct 504 ms 199028 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 188328 KB Output is correct
2 Correct 2183 ms 284716 KB Output is correct
3 Correct 2802 ms 286364 KB Output is correct
4 Correct 879 ms 283016 KB Output is correct
5 Correct 3495 ms 304760 KB Output is correct
6 Correct 2924 ms 286292 KB Output is correct
7 Correct 1326 ms 220212 KB Output is correct
8 Correct 368 ms 219728 KB Output is correct
9 Correct 1469 ms 222624 KB Output is correct
10 Correct 1282 ms 220520 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 188632 KB Output is correct
2 Correct 422 ms 199504 KB Output is correct
3 Correct 506 ms 199176 KB Output is correct
4 Correct 500 ms 199112 KB Output is correct
5 Correct 481 ms 199320 KB Output is correct
6 Correct 259 ms 199000 KB Output is correct
7 Correct 489 ms 199068 KB Output is correct
8 Correct 481 ms 199112 KB Output is correct
9 Correct 526 ms 199420 KB Output is correct
10 Correct 259 ms 199056 KB Output is correct
11 Correct 504 ms 199028 KB Output is correct
12 Correct 67 ms 188328 KB Output is correct
13 Correct 2183 ms 284716 KB Output is correct
14 Correct 2802 ms 286364 KB Output is correct
15 Correct 879 ms 283016 KB Output is correct
16 Correct 3495 ms 304760 KB Output is correct
17 Correct 2924 ms 286292 KB Output is correct
18 Correct 1326 ms 220212 KB Output is correct
19 Correct 368 ms 219728 KB Output is correct
20 Correct 1469 ms 222624 KB Output is correct
21 Correct 1282 ms 220520 KB Output is correct
22 Correct 2668 ms 287704 KB Output is correct
23 Correct 2713 ms 288352 KB Output is correct
24 Correct 3674 ms 289240 KB Output is correct
25 Correct 3677 ms 290544 KB Output is correct
26 Correct 3681 ms 289768 KB Output is correct
27 Correct 4525 ms 307752 KB Output is correct
28 Correct 996 ms 310620 KB Output is correct
29 Correct 3683 ms 312900 KB Output is correct
30 Correct 3692 ms 312404 KB Output is correct
31 Correct 3868 ms 313004 KB Output is correct
32 Correct 1321 ms 231908 KB Output is correct
33 Correct 356 ms 228508 KB Output is correct
34 Correct 1052 ms 227904 KB Output is correct
35 Correct 1018 ms 227776 KB Output is correct
36 Correct 1347 ms 228172 KB Output is correct
37 Correct 1316 ms 228220 KB Output is correct