oj.uz

Submission #861923

# Submission time Handle Problem Language Result Execution time Memory
861923 2023-10-17T07:40:52 Z mgl_diamond Factories (JOI14_factories) C++17
100 / 100
 1520 ms 200588 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 18 ms 45660 KB Output is correct
2 Correct 517 ms 61496 KB Output is correct
3 Correct 479 ms 61412 KB Output is correct
4 Correct 501 ms 59548 KB Output is correct
5 Correct 465 ms 61740 KB Output is correct
6 Correct 336 ms 55388 KB Output is correct
7 Correct 452 ms 61412 KB Output is correct
8 Correct 479 ms 61568 KB Output is correct
9 Correct 454 ms 59616 KB Output is correct
10 Correct 326 ms 46100 KB Output is correct
11 Correct 450 ms 53348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 43624 KB Output is correct
2 Correct 877 ms 175296 KB Output is correct
3 Correct 887 ms 177112 KB Output is correct
4 Correct 660 ms 175736 KB Output is correct
5 Correct 918 ms 199696 KB Output is correct
6 Correct 947 ms 178324 KB Output is correct
7 Correct 569 ms 81744 KB Output is correct
8 Correct 416 ms 80072 KB Output is correct
9 Correct 482 ms 83208 KB Output is correct
10 Correct 577 ms 79360 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 45660 KB Output is correct
2 Correct 517 ms 61496 KB Output is correct
3 Correct 479 ms 61412 KB Output is correct
4 Correct 501 ms 59548 KB Output is correct
5 Correct 465 ms 61740 KB Output is correct
6 Correct 336 ms 55388 KB Output is correct
7 Correct 452 ms 61412 KB Output is correct
8 Correct 479 ms 61568 KB Output is correct
9 Correct 454 ms 59616 KB Output is correct
10 Correct 326 ms 46100 KB Output is correct
11 Correct 450 ms 53348 KB Output is correct
12 Correct 7 ms 43624 KB Output is correct
13 Correct 877 ms 175296 KB Output is correct
14 Correct 887 ms 177112 KB Output is correct
15 Correct 660 ms 175736 KB Output is correct
16 Correct 918 ms 199696 KB Output is correct
17 Correct 947 ms 178324 KB Output is correct
18 Correct 569 ms 81744 KB Output is correct
19 Correct 416 ms 80072 KB Output is correct
20 Correct 482 ms 83208 KB Output is correct
21 Correct 577 ms 79360 KB Output is correct
22 Correct 1520 ms 181148 KB Output is correct
23 Correct 1384 ms 182036 KB Output is correct
24 Correct 1512 ms 183440 KB Output is correct
25 Correct 1439 ms 187336 KB Output is correct
26 Correct 1330 ms 182480 KB Output is correct
27 Correct 1480 ms 200588 KB Output is correct
28 Correct 983 ms 184156 KB Output is correct
29 Correct 1277 ms 182096 KB Output is correct
30 Correct 1298 ms 183632 KB Output is correct
31 Correct 1247 ms 182388 KB Output is correct
32 Correct 746 ms 90064 KB Output is correct
33 Correct 523 ms 86564 KB Output is correct
34 Correct 674 ms 84308 KB Output is correct
35 Correct 627 ms 84300 KB Output is correct
36 Correct 588 ms 84692 KB Output is correct
37 Correct 585 ms 85072 KB Output is correct