oj.uz

Submission #861924

# Submission time Handle Problem Language Result Execution time Memory
861924 2023-10-17T07:41:40 Z mgl_diamond Factories (JOI14_factories) C++17
100 / 100
 1385 ms 199640 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
 
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define file "input"
 
void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
 
  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}
 
const ll BIG = 1e18;
const int N = 5e5+5, LOG = 20;
int n, q;
vector<ii> graph[N];
 
int cnt, anc[N*2][LOG], st[N], en[N], high[N], lg[N*2];
ll distb[N], distr[N], curpar[N], wei[N];
vector<int> node;
bool red[N], blue[N];
 
void dfs_prep(int u, int p) {
  anc[++cnt][0] = u;
  st[u] = cnt;
  fore(x, graph[u]) if (x.first != p) {
    wei[x.first] = wei[u] + x.second;
    high[x.first] = high[u] + 1;
    dfs_prep(x.first, u);
    anc[++cnt][0] = u;
  }
  en[u] = cnt;
}
 
int comb(int i, int j) {
  return high[i] < high[j] ? i : j;
}

int lca(int u, int v) {
  u = st[u]; v = st[v];
  if (u > v) swap(u, v);
  int k = lg[v-u+1];
  return comb(anc[u][k], anc[v-(1<<k)+1][k]);
}
 
void Init(int N, int A[], int B[], int D[]) {
  n = N;
  foru(i, 0, n-2) {
    graph[A[i]+1].emplace_back(B[i]+1, D[i]);
    graph[B[i]+1].emplace_back(A[i]+1, D[i]);
  }

  dfs_prep(1, 0);
  foru(i, 2, cnt) lg[i] = lg[i >> 1] + 1;
  foru(i, 1, LOG-1) foru(j, 1, cnt-(1<<i)+1) anc[j][i] = comb(anc[j][i-1], anc[j+(1<<(i-1))][i-1]);
}
 
ll Query(int S, int X[], int T, int Y[]) {
  foru(i, 0, S-1) {
    int v = X[i]+1;
    node.push_back(v);
    red[v] = 1;
  }
 
  foru(i, 0, T-1) {
    int v = Y[i]+1;
    node.push_back(v);
    blue[v] = 1;
  }
 
  sort(all(node), [&](int x, int y){
    return st[x] < st[y];
  });
 
  int m = sz(node)-2;
  foru(i, 0, m) node.push_back(lca(node[i], node[i+1]));
 
  sort(all(node), [&](int x, int y){
    return st[x] < st[y];
  });
  node.resize(unique(all(node)) - node.begin());
 
  stack<int> tmp;
  fore(u, node) {
    distb[u] = distr[u] = BIG;
    curpar[u] = 0;
    while (!tmp.empty()) {
      if (en[tmp.top()] < st[u]) tmp.pop();
      else {
        curpar[u] = tmp.top();
        break;
      }
    }
    tmp.push(u);
  }
 
  ll ans = BIG;
  ford(i, sz(node)-1, 0) {
    int u = node[i];
    if (blue[u]) distb[u] = 0;
    if (red[u]) distr[u] = 0;
    ans = min(ans, distb[u] + distr[u]);
 
    if (curpar[u] > 0) {
      distb[curpar[u]] = min(distb[curpar[u]], distb[u] + wei[u] - wei[curpar[u]]);
      distr[curpar[u]] = min(distr[curpar[u]], distr[u] + wei[u] - wei[curpar[u]]);
    }
  }
 
  fore(u, node) {
    blue[u] = red[u] = 0;
  }
  node.clear();
 
  return ans;
}

Compilation message

factories.cpp: In function 'void setIO()':
factories.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 45660 KB Output is correct
2 Correct 494 ms 61532 KB Output is correct
3 Correct 448 ms 61524 KB Output is correct
4 Correct 468 ms 61552 KB Output is correct
5 Correct 449 ms 61776 KB Output is correct
6 Correct 317 ms 61776 KB Output is correct
7 Correct 448 ms 61484 KB Output is correct
8 Correct 485 ms 61528 KB Output is correct
9 Correct 457 ms 61796 KB Output is correct
10 Correct 310 ms 61396 KB Output is correct
11 Correct 447 ms 61484 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 45660 KB Output is correct
2 Correct 788 ms 175128 KB Output is correct
3 Correct 792 ms 177372 KB Output is correct
4 Correct 596 ms 175736 KB Output is correct
5 Correct 792 ms 199504 KB Output is correct
6 Correct 815 ms 178768 KB Output is correct
7 Correct 502 ms 85588 KB Output is correct
8 Correct 403 ms 85868 KB Output is correct
9 Correct 443 ms 88536 KB Output is correct
10 Correct 505 ms 86352 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 45660 KB Output is correct
2 Correct 494 ms 61532 KB Output is correct
3 Correct 448 ms 61524 KB Output is correct
4 Correct 468 ms 61552 KB Output is correct
5 Correct 449 ms 61776 KB Output is correct
6 Correct 317 ms 61776 KB Output is correct
7 Correct 448 ms 61484 KB Output is correct
8 Correct 485 ms 61528 KB Output is correct
9 Correct 457 ms 61796 KB Output is correct
10 Correct 310 ms 61396 KB Output is correct
11 Correct 447 ms 61484 KB Output is correct
12 Correct 8 ms 45660 KB Output is correct
13 Correct 788 ms 175128 KB Output is correct
14 Correct 792 ms 177372 KB Output is correct
15 Correct 596 ms 175736 KB Output is correct
16 Correct 792 ms 199504 KB Output is correct
17 Correct 815 ms 178768 KB Output is correct
18 Correct 502 ms 85588 KB Output is correct
19 Correct 403 ms 85868 KB Output is correct
20 Correct 443 ms 88536 KB Output is correct
21 Correct 505 ms 86352 KB Output is correct
22 Correct 1385 ms 181204 KB Output is correct
23 Correct 1220 ms 182464 KB Output is correct
24 Correct 1333 ms 184016 KB Output is correct
25 Correct 1283 ms 185488 KB Output is correct
26 Correct 1170 ms 182544 KB Output is correct
27 Correct 1380 ms 199640 KB Output is correct
28 Correct 909 ms 184068 KB Output is correct
29 Correct 1170 ms 181584 KB Output is correct
30 Correct 1165 ms 179536 KB Output is correct
31 Correct 1124 ms 179644 KB Output is correct
32 Correct 688 ms 88784 KB Output is correct
33 Correct 478 ms 85312 KB Output is correct
34 Correct 630 ms 83024 KB Output is correct
35 Correct 617 ms 83540 KB Output is correct
36 Correct 587 ms 83668 KB Output is correct
37 Correct 619 ms 83648 KB Output is correct