oj.uz

Submission #682070

# Submission time Handle Problem Language Result Execution time Memory
682070 2023-01-15T15:08:43 Z vjudge1 Factories (JOI14_factories) C++17
100 / 100
 1232 ms 269920 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;

const int lim = 1e6 + 5, lim2 = 20;
struct sparse_table {
  ll a[lim2][lim];
  int logz[lim];
  sparse_table() {
    logz[1] = 0;
    for(int i = 2; i < lim; ++i)
      logz[i] = logz[i / 2] + 1;
  }
  void build() {
    for(int i = 1; i < lim2; ++i) {
      for(int j = 0; j + (1 << (i - 1)) < lim; ++j) {
        a[i][j] = min(a[i - 1][j], a[i - 1][j + (1 << (i - 1))]);
      }
    }
  }

  ll query(int l, int r) {
    int lg = logz[r - l + 1];
    //cout << l << " " << r << " " << lg << " " << a[lg][l] << " " << a[lg][r - (1 << lg) + 1] << endl;
    return min(a[lg][l], a[lg][r - (1 << lg) + 1]);
  }
};
// sp -> dist from root at ett index i (se is nd)
sparse_table sp;
// ett -> ett number i itu node brp
// inv -> node i itu ett number paling kecilnya berapa
// depth -> dist from root
int ett[lim], inv[lim], t = 0;
ll depth[lim];
vector<pair<int, int>> edges[lim];
bool vis[lim];
void dfs(int nd) {
  vis[nd] = 1;
  ett[t] = nd;
  inv[nd] = t;
  ++t;
  for(auto i : edges[nd]) {
    if(!vis[i.fi]) {
      depth[i.fi] = depth[nd] + i.se;
      dfs(i.fi);
      ett[t++] = nd;
    }
  }
}

void Init(int N, int A[], int B[], int D[]) {
  for(int i = 0; i < N - 1; ++i) {
    edges[A[i]].push_back(make_pair(B[i], D[i]));
    edges[B[i]].push_back(make_pair(A[i], D[i]));
  }
  dfs(0);
  for(int i = 0; i < t; ++i)
    sp.a[0][i] = depth[ett[i]];
  sp.build();
  for(int i = 0; i < t; ++i)
    sp.query(i, i);
}

ll ans;
struct disjoint_set {
  vector<int> head, sz;
  vector<ll> minx, miny;
  disjoint_set(int a) {
    head = vector<int>(a, -1);
    sz = vector<int>(a, 1);
    minx = miny = vector<ll>(a, 1e18);
  }
  int fh(int nd) {
    while(head[nd] != -1) {
      nd = head[nd];
    }
    return nd;
  }
  bool merge(int x, int y, ll h) {
    x = fh(x), y = fh(y);
    if(x != y) {
      if(sz[x] < sz[y])
        swap(x, y);
        sz[x] += sz[y];
        head[y] = x;
        minx[x] = min(minx[x], minx[y]);
        miny[x] = min(miny[x], miny[y]);
        ans = min(ans, minx[x] + miny[x] - 2 * h);
    }
    return x != y;
  }
};

long long Query(int S, int X[], int T, int Y[]) {
  // sort by ett
  // fi -> ett
  // se -> type
  pair<int, bool> a[S + T];
  for(int i = 0; i < S; ++i)
    a[i] = make_pair(inv[X[i]], 0);
  for(int i = 0; i < T; ++i)
    a[i + S] = make_pair(inv[Y[i]], 1);
  sort(a, a + S + T);
  disjoint_set dsu(S + T);
  for(int i = 0; i < S + T; ++i) {
    if(a[i].se)
      dsu.miny[i] = sp.query(a[i].fi, a[i].fi);
    else
      dsu.minx[i] = sp.query(a[i].fi, a[i].fi);
  }
  // fi -> lca depth
  // se -> pair of nodes
  pair<ll, pair<int, int>> b[S + T - 1];
  for(int i = 0; i < S + T - 1; ++i) {
    b[i] = make_pair(sp.query(a[i].fi, a[i + 1].fi), make_pair(i, i + 1));
  }
  sort(b, b + S + T - 1, greater<pair<ll, pair<int, int>>>());
  ans = 1e18;
  for(int i = 0; i < S + T - 1; ++i) {
    dsu.merge(b[i].se.fi, b[i].se.se, b[i].fi);
  }
  return ans;
}

Compilation message

factories.cpp: In member function 'bool disjoint_set::merge(int, int, long long int)':
factories.cpp:85:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   85 |       if(sz[x] < sz[y])
      |       ^~
factories.cpp:87:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   87 |         sz[x] += sz[y];
      |         ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 172748 KB Output is correct
2 Correct 526 ms 180948 KB Output is correct
3 Correct 468 ms 180836 KB Output is correct
4 Correct 480 ms 180948 KB Output is correct
5 Correct 503 ms 181056 KB Output is correct
6 Correct 415 ms 180964 KB Output is correct
7 Correct 489 ms 180916 KB Output is correct
8 Correct 466 ms 180960 KB Output is correct
9 Correct 532 ms 181212 KB Output is correct
10 Correct 411 ms 181000 KB Output is correct
11 Correct 451 ms 180828 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 172508 KB Output is correct
2 Correct 767 ms 221952 KB Output is correct
3 Correct 772 ms 241372 KB Output is correct
4 Correct 626 ms 240924 KB Output is correct
5 Correct 853 ms 264688 KB Output is correct
6 Correct 814 ms 243572 KB Output is correct
7 Correct 567 ms 204468 KB Output is correct
8 Correct 559 ms 205324 KB Output is correct
9 Correct 541 ms 208216 KB Output is correct
10 Correct 591 ms 205980 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 172748 KB Output is correct
2 Correct 526 ms 180948 KB Output is correct
3 Correct 468 ms 180836 KB Output is correct
4 Correct 480 ms 180948 KB Output is correct
5 Correct 503 ms 181056 KB Output is correct
6 Correct 415 ms 180964 KB Output is correct
7 Correct 489 ms 180916 KB Output is correct
8 Correct 466 ms 180960 KB Output is correct
9 Correct 532 ms 181212 KB Output is correct
10 Correct 411 ms 181000 KB Output is correct
11 Correct 451 ms 180828 KB Output is correct
12 Correct 86 ms 172508 KB Output is correct
13 Correct 767 ms 221952 KB Output is correct
14 Correct 772 ms 241372 KB Output is correct
15 Correct 626 ms 240924 KB Output is correct
16 Correct 853 ms 264688 KB Output is correct
17 Correct 814 ms 243572 KB Output is correct
18 Correct 567 ms 204468 KB Output is correct
19 Correct 559 ms 205324 KB Output is correct
20 Correct 541 ms 208216 KB Output is correct
21 Correct 591 ms 205980 KB Output is correct
22 Correct 1221 ms 251368 KB Output is correct
23 Correct 1232 ms 253732 KB Output is correct
24 Correct 1148 ms 251724 KB Output is correct
25 Correct 1144 ms 254036 KB Output is correct
26 Correct 1068 ms 249764 KB Output is correct
27 Correct 1223 ms 269920 KB Output is correct
28 Correct 943 ms 255916 KB Output is correct
29 Correct 1086 ms 249796 KB Output is correct
30 Correct 1010 ms 248992 KB Output is correct
31 Correct 1087 ms 249548 KB Output is correct
32 Correct 634 ms 210128 KB Output is correct
33 Correct 576 ms 208980 KB Output is correct
34 Correct 660 ms 202480 KB Output is correct
35 Correct 644 ms 202448 KB Output is correct
36 Correct 642 ms 202888 KB Output is correct
37 Correct 585 ms 202828 KB Output is correct