Submission #861923

#	Time	Username	Problem	Language	Result	Execution time	Memory
861923		mgl_diamond	Factories (JOI14_factories)	C++17	100 / 100	1520 ms	200588 KiB

factories

// #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 (stderr)

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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67