oj.uz

Submission #861763

# Submission time Handle Problem Language Result Execution time Memory
861763 2023-10-17T02:06:08 Z mgl_diamond Factories (JOI14_factories) C++17
0 / 100
 11 ms 37464 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 int N = 5e5+5, LOG = 19;
int n, q;
vector<ii> graph[N];
 
int cnt, anc[N][LOG], st[N], en[N], wei[N];
ll distb[N], distr[N], curpar[N];
 
vector<int> node;
bool red[N], blue[N];
 
void dfs_prep(int u, int p) {
  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]);
  }
}
 
long long Query(int S, int X[], int T, int Y[]) {
  foru(i, 0, S-1) {
    int v = X[i];
    cin >> v; ++v;
    node.push_back(v);
    red[v] = 1;
  }
 
  foru(i, 0, T-1) {
    int v = Y[i];
    cin >> v; ++v;
    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] = N;
    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 = N;
  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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 37464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 37208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 37464 KB Output isn't correct
2 Halted 0 ms 0 KB -