oj.uz

Submission #861782

# Submission time Handle Problem Language Result Execution time Memory
861782 2023-10-17T02:27:00 Z mgl_diamond Factories (JOI14_factories) C++17
100 / 100
 1877 ms 156024 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 = 19;
int n, q;
vector<ii> graph[N];

int cnt, anc[N][LOG], st[N], en[N];
ll distb[N], distr[N], curpar[N], wei[N];
vector<int> node;
bool red[N], blue[N];

void dfs_prep(int u, int p) {
//  cout << u << "\n";
  anc[u][0] = p;
  foru(i, 1, LOG-1) anc[u][i] = anc[anc[u][i-1]][i-1];
  st[u] = ++cnt;
  fore(x, graph[u]) if (x.first != p) {
    wei[x.first] = wei[u] + x.second;
    dfs_prep(x.first, u);
  }
  en[u] = cnt;
}

bool isanc(int u, int v) {
  return st[u] <= st[v] && en[v] <= en[u];
}

int lca(int u, int v) {
  if (isanc(u, v)) return u;
  ford(i, LOG-1, 0) {
    int tmp = anc[u][i];
    if (!isanc(tmp, v)) u = tmp;
  }
  return anc[u][0];
}

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]);
  }

  en[0] = n+1;
  dfs_prep(1, 0);
}

long long 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];
//    cout << u << "\n";
    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 19 ms 45404 KB Output is correct
2 Correct 621 ms 57336 KB Output is correct
3 Correct 591 ms 57320 KB Output is correct
4 Correct 588 ms 57396 KB Output is correct
5 Correct 446 ms 57836 KB Output is correct
6 Correct 512 ms 57352 KB Output is correct
7 Correct 581 ms 57176 KB Output is correct
8 Correct 592 ms 57416 KB Output is correct
9 Correct 446 ms 57556 KB Output is correct
10 Correct 495 ms 57172 KB Output is correct
11 Correct 578 ms 57320 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 43352 KB Output is correct
2 Correct 931 ms 130624 KB Output is correct
3 Correct 1185 ms 132484 KB Output is correct
4 Correct 744 ms 130948 KB Output is correct
5 Correct 770 ms 154692 KB Output is correct
6 Correct 1249 ms 133456 KB Output is correct
7 Correct 886 ms 72420 KB Output is correct
8 Correct 585 ms 72496 KB Output is correct
9 Correct 437 ms 75460 KB Output is correct
10 Correct 800 ms 73160 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 45404 KB Output is correct
2 Correct 621 ms 57336 KB Output is correct
3 Correct 591 ms 57320 KB Output is correct
4 Correct 588 ms 57396 KB Output is correct
5 Correct 446 ms 57836 KB Output is correct
6 Correct 512 ms 57352 KB Output is correct
7 Correct 581 ms 57176 KB Output is correct
8 Correct 592 ms 57416 KB Output is correct
9 Correct 446 ms 57556 KB Output is correct
10 Correct 495 ms 57172 KB Output is correct
11 Correct 578 ms 57320 KB Output is correct
12 Correct 8 ms 43352 KB Output is correct
13 Correct 931 ms 130624 KB Output is correct
14 Correct 1185 ms 132484 KB Output is correct
15 Correct 744 ms 130948 KB Output is correct
16 Correct 770 ms 154692 KB Output is correct
17 Correct 1249 ms 133456 KB Output is correct
18 Correct 886 ms 72420 KB Output is correct
19 Correct 585 ms 72496 KB Output is correct
20 Correct 437 ms 75460 KB Output is correct
21 Correct 800 ms 73160 KB Output is correct
22 Correct 1707 ms 136252 KB Output is correct
23 Correct 1531 ms 137472 KB Output is correct
24 Correct 1691 ms 138392 KB Output is correct
25 Correct 1664 ms 140436 KB Output is correct
26 Correct 1863 ms 137796 KB Output is correct
27 Correct 1259 ms 156024 KB Output is correct
28 Correct 1170 ms 139080 KB Output is correct
29 Correct 1836 ms 137464 KB Output is correct
30 Correct 1873 ms 136916 KB Output is correct
31 Correct 1877 ms 137484 KB Output is correct
32 Correct 679 ms 76744 KB Output is correct
33 Correct 680 ms 73428 KB Output is correct
34 Correct 866 ms 71252 KB Output is correct
35 Correct 866 ms 71196 KB Output is correct
36 Correct 903 ms 71504 KB Output is correct
37 Correct 868 ms 71788 KB Output is correct