oj.uz

Submission #708535

# Submission time Handle Problem Language Result Execution time Memory
708535 2023-03-12T03:07:14 Z joelgun14 Factories (JOI14_factories) C++17
100 / 100
 1421 ms 246756 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 96 ms 172904 KB Output is correct
2 Correct 526 ms 182272 KB Output is correct
3 Correct 537 ms 182032 KB Output is correct
4 Correct 502 ms 182212 KB Output is correct
5 Correct 530 ms 182568 KB Output is correct
6 Correct 423 ms 186044 KB Output is correct
7 Correct 469 ms 185824 KB Output is correct
8 Correct 482 ms 185960 KB Output is correct
9 Correct 522 ms 185812 KB Output is correct
10 Correct 439 ms 185652 KB Output is correct
11 Correct 467 ms 184268 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 172488 KB Output is correct
2 Correct 769 ms 222048 KB Output is correct
3 Correct 786 ms 223656 KB Output is correct
4 Correct 635 ms 223456 KB Output is correct
5 Correct 873 ms 246756 KB Output is correct
6 Correct 879 ms 225064 KB Output is correct
7 Correct 592 ms 192660 KB Output is correct
8 Correct 494 ms 193232 KB Output is correct
9 Correct 577 ms 196160 KB Output is correct
10 Correct 584 ms 193896 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 172904 KB Output is correct
2 Correct 526 ms 182272 KB Output is correct
3 Correct 537 ms 182032 KB Output is correct
4 Correct 502 ms 182212 KB Output is correct
5 Correct 530 ms 182568 KB Output is correct
6 Correct 423 ms 186044 KB Output is correct
7 Correct 469 ms 185824 KB Output is correct
8 Correct 482 ms 185960 KB Output is correct
9 Correct 522 ms 185812 KB Output is correct
10 Correct 439 ms 185652 KB Output is correct
11 Correct 467 ms 184268 KB Output is correct
12 Correct 85 ms 172488 KB Output is correct
13 Correct 769 ms 222048 KB Output is correct
14 Correct 786 ms 223656 KB Output is correct
15 Correct 635 ms 223456 KB Output is correct
16 Correct 873 ms 246756 KB Output is correct
17 Correct 879 ms 225064 KB Output is correct
18 Correct 592 ms 192660 KB Output is correct
19 Correct 494 ms 193232 KB Output is correct
20 Correct 577 ms 196160 KB Output is correct
21 Correct 584 ms 193896 KB Output is correct
22 Correct 1350 ms 227540 KB Output is correct
23 Correct 1184 ms 229644 KB Output is correct
24 Correct 1185 ms 227860 KB Output is correct
25 Correct 1242 ms 229776 KB Output is correct
26 Correct 1162 ms 225876 KB Output is correct
27 Correct 1421 ms 245780 KB Output is correct
28 Correct 1006 ms 231340 KB Output is correct
29 Correct 1000 ms 225432 KB Output is correct
30 Correct 1070 ms 225464 KB Output is correct
31 Correct 1038 ms 225612 KB Output is correct
32 Correct 634 ms 200304 KB Output is correct
33 Correct 560 ms 199152 KB Output is correct
34 Correct 663 ms 192872 KB Output is correct
35 Correct 660 ms 193424 KB Output is correct
36 Correct 620 ms 193776 KB Output is correct
37 Correct 621 ms 194012 KB Output is correct