Submission #1312337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312337		reginox	Factories (JOI14_factories)	C++20	100 / 100	1954 ms	161040 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll rd(ll l, ll r){
  return rng() % (r-l+1) + l;
}

const int N = 5e5+3;
int n, q;
vector<pair<int, ll>> g[N], g2[N];
int tin[N], tout[N] = {500069}, timer;
ll pf[N];
int sp[N][20];

void dfs(int u, int p){
  for(int i = 1; i <= 19; i++) sp[u][i] = sp[sp[u][i-1]][i-1];
  tin[u] = ++timer;
  for(auto [v, w]:g[u]){
    if(v == p) continue;
    sp[v][0] = u;
    pf[v] = pf[u] + w;
    dfs(v, u);
  }
  tout[u] = timer;
}

int lca(int u, int v){
  if(tin[u] <= tin[v] && tout[v] <= tout[u]) return u;
  for(int i = 19; i >= 0; i--){
    if(!(tin[sp[u][i]] <= tin[v] && tout[v] <= tout[sp[u][i]])){
      u = sp[u][i];
    }
  }
  return sp[u][0];
}

int c[N];
bool vis[N];
pair<ll, ll> dis[N];
ll ans = 0;

void dfs2(int u, int p){
  vis[u] = true;
  if(c[u] == 1) dis[u].first = 0;
  else if(c[u] == 2) dis[u].second = 0;
  for(auto [v, w]:g2[u]){
    if(v == p) continue;
    dfs2(v, u);
    dis[u].first = min(dis[u].first, dis[v].first + w);
    dis[u].second = min(dis[u].second, dis[v].second + w);
  }
  ans = min(ans, dis[u].first + dis[u].second);
  return ;
}

void Init(int N, int A[], int B[], int D[]){
  n = N;
  for(int i = 0; i < n-1; i++){
    g[A[i]+1].push_back({B[i]+1, D[i]});
    g[B[i]+1].push_back({A[i]+1, D[i]});
  }
  dfs(1, 0);
  memset(dis, 0x3f, sizeof(dis));
  return ;
}

long long Query(int s, int X[], int t, int Y[]){
  vector<int> v;
  for(int i = 0; i < s; i++){
    v.push_back(X[i]+1);
    c[X[i]+1] = 1;
  }
  for(int i = 0; i < t; i++){
    v.push_back(Y[i]+1);
    c[Y[i]+1] = 2;
  }
  sort(all(v), [&](int a, int b){
    return tin[a] < tin[b];
  });
  vector<int> t2;
  for(int i = 0; i < s+t-1; i++){
    t2.push_back(v[i]);
    t2.push_back(lca(v[i], v[i+1]));
  }
  t2.push_back(v[s+t-1]);
  sort(all(t2)); t2.erase(unique(all(t2)), t2.end());
  sort(all(t2), [&](int a, int b){
    return tin[a] < tin[b];
  });
  vector<int> nx(t2.size()+1);
  for(int i = t2.size()-1; i >= 0; i--){
    int l = i+1, r = t2.size() - 1;
    while(l <= r){
      int mid = (l+r)/2;
      if(tin[t2[mid]] <= tout[t2[i]]) l = mid+1;
      else r = mid-1;
    }
    nx[i] = l;
  }
  for(int i = t2.size() - 1; i >= 0; i--){
    for(int j = i+1; j <= nx[i]-1;){
      g2[t2[i]].push_back({t2[j], pf[t2[j]] - pf[t2[i]]});
      j = nx[j];
    }
  }
  ans = 4e18;
  for(auto x:t2){
    if(!vis[x]) dfs2(x, 0);
  }
  for(auto x:t2){
    g2[x].clear();
    vis[x] = false;
    c[x] = 0;
    dis[x] = {1e18, 1e18};
  }
  t2.clear();
  return ans;
}


// #define MAX_N          500000
// #define MAX_Q          100000
// #define MAX_SUM_ST    1000000
// #define MAX_VALUE  1000000000

// static int NN, Q;
// static int A[MAX_N], B[MAX_N], D[MAX_N];
// static int S[MAX_N];
// static int T[MAX_N];
// static int X[MAX_SUM_ST];
// static int Y[MAX_SUM_ST];

// static int Qx[MAX_N];
// static int Qy[MAX_N];

// int main() {

//   int i, j, k;
//   int STop, TTop;

//   if (2 != scanf("%d%d", &NN, &Q)) {
//     fprintf(stderr, "error: cannot read N and Q.\n");
//     exit(1);
//   }
//   if (!(2 <= NN && NN <= MAX_N)) {
//     fprintf(stderr, "error: N is out of bounds.\n");
//     exit(1);
//   }
//   if (!(1 <= Q && Q <= MAX_Q)) {
//     fprintf(stderr, "error: Q is out of bounds.\n");
//     exit(1);
//   }
//   for (i = 0; i < NN - 1; ++i) {
//     if (1 != scanf("%d", &A[i])) {
//       fprintf(stderr, "error: cannot read A[%d].\n", i);
//       exit(1);
//     }
//     if (!(0 <= A[i] && A[i] <= NN - 1)) {
//       fprintf(stderr, "error: A[%d] is out of bounds.\n", i);
//       exit(1);
//     }
//     if (1 != scanf("%d", &B[i])) {
//       fprintf(stderr, "error: cannot read B[%d].\n", i);
//       exit(1);
//     }
//     if (!(0 <= B[i] && B[i] <= NN - 1)) {
//       fprintf(stderr, "error: B[%d] is out of bounds.\n", i);
//       exit(1);
//     }
//     if (A[i] == B[i]) {
//       fprintf(stderr, "error: B[%d] is equal to A[%d].\n", i, i);
//       exit(1);
//     }
//     if (1 != scanf("%d", &D[i])) {
//       fprintf(stderr, "error: cannot read D[%d].\n", i);
//       exit(1);
//     }
//     if (!(1 <= D[i] && D[i] <= MAX_VALUE)) {
//       fprintf(stderr, "error: D[%d] is out of bounds.\n", i);
//       exit(1);
//     }
//   }

//   STop = 0;
//   TTop = 0;

//   for (j = 0; j < Q; ++j) {
//     if (2 != scanf("%d%d", &S[j], &T[j])) {
//       fprintf(stderr, "error: cannot read L[%d] and R[%d].\n", j, j);
//       exit(1);
//     }

//     if(STop + S[j] > MAX_SUM_ST) {
//       fprintf(stderr, "error: S[0] + S[1] + ... + S[%d] is out of bounds.\n", j);
//       exit(1);
//     }

//     if(TTop + T[j] > MAX_SUM_ST) {
//       fprintf(stderr, "error: T[0] + T[1] + ... + T[%d] is out of bounds.\n", j);
//       exit(1);
//     }

//     for (k = 0; k < S[j]; ++k, ++STop) {
//       if (1 != scanf("%d", &X[STop])) {
//         fprintf(stderr, "error: cannot read X[%d][%d].\n", j, k);
//         exit(1);
//       }

//       if (!(0 <= X[STop] && X[STop] <= NN - 1)) {
//         fprintf(stderr, "error: cannot read X[%d][%d].\n", j, k);
//         exit(1);
//       }
//     }

//     for (k = 0; k < T[j]; ++k, ++TTop) {
//       if (1 != scanf("%d", &Y[TTop])) {
//         fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k);
//         exit(1);
//       }

//       if (!(0 <= Y[TTop] && Y[TTop] <= NN - 1)) {
//         fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k);
//         exit(1);
//       }
//     }
//   }

//   STop = 0;
//   TTop = 0;
//   Init(NN, A, B, D);

//   for (j = 0; j < Q; ++j) {
//     for (k = 0; k < S[j]; k++) {
//         Qx[k] = X[STop++];
//     }
//     for (k = 0; k < T[j]; k++) {
//         Qy[k] = Y[TTop++];
//     }

//     printf("%lld\n", Query(S[j], Qx, T[j], Qy));
//   }


//   return 0;
// }

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67