oj.uz

Submission #682069

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

const int lim = 5e5 + 5, lim2 = 19;
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 53 ms 83020 KB Output is correct
2 Correct 492 ms 100488 KB Output is correct
3 Correct 449 ms 100332 KB Output is correct
4 Correct 461 ms 100508 KB Output is correct
5 Correct 501 ms 100644 KB Output is correct
6 Correct 394 ms 100428 KB Output is correct
7 Correct 421 ms 100324 KB Output is correct
8 Correct 499 ms 100536 KB Output is correct
9 Correct 472 ms 100608 KB Output is correct
10 Correct 398 ms 100628 KB Output is correct
11 Correct 436 ms 100340 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 82636 KB Output is correct
2 Runtime error 582 ms 131748 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 83020 KB Output is correct
2 Correct 492 ms 100488 KB Output is correct
3 Correct 449 ms 100332 KB Output is correct
4 Correct 461 ms 100508 KB Output is correct
5 Correct 501 ms 100644 KB Output is correct
6 Correct 394 ms 100428 KB Output is correct
7 Correct 421 ms 100324 KB Output is correct
8 Correct 499 ms 100536 KB Output is correct
9 Correct 472 ms 100608 KB Output is correct
10 Correct 398 ms 100628 KB Output is correct
11 Correct 436 ms 100340 KB Output is correct
12 Correct 47 ms 82636 KB Output is correct
13 Runtime error 582 ms 131748 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -