Submission #40257

#	Time	Username	Problem	Language	Result	Execution time	Memory
40257		krauch	Factories (JOI14_factories)	C++14	33 / 100	6000 ms	455072 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"

#include <stdio.h>
#include <stdlib.h>

using namespace std;

typedef long long ll;

#define mkp make_pair
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define eb emplace_back
#define F first
#define S second

const ll ool = 1e18 + 9;
const int NN = 1e6 + 6, C = 20, oo = 1e9 + 9;

int n, tin[NN], timer, lg[NN];
bool tp1[NN], tp2[NN];
ll lvl[NN], d[NN][2];
pair < ll, int > mn[C + 1][NN];
vector < pair < int, ll > > g[NN];

void dfs(int v, int par) {
    tin[v] = ++timer;
    mn[0][timer] = mkp(lvl[v], v);
    if (timer > 1) lg[timer] = lg[timer >> 1] + 1;
    for (auto it : g[v]) {
        int to = it.F;
        if (to == par) continue;
        lvl[to] = lvl[v] + it.S;
        dfs(to, v);
        mn[0][++timer] = mkp(lvl[v], v);
        if (timer > 1) lg[timer] = lg[timer >> 1] + 1;
    }
}

ll dfs2(int v, int par) {
    d[v][0] = d[v][1] = ool;
    ll res = ool;
    if (tp1[v]) d[v][0] = 0;
    if (tp2[v]) d[v][1] = 0;
    for (auto it : g[v]) {
        int to = it.F;
        if (to == par) continue;
        res = min(res, dfs2(to, v));
        d[v][0] = min(d[v][0], d[to][0] + it.S);
        d[v][1] = min(d[v][1], d[to][1] + it.S);
    }
    //cerr << v << " " << d[v][0] << " " << d[v][1] << "\n";
    return min(res, d[v][0] + d[v][1]);
}

int get(int l, int r) {
    if (l > r) swap(l, r);
    int deg = lg[r - l + 1];
    return min(mn[deg][l], mn[deg][r - (1 << deg) + 1]).S;
}

void Init(int _n, int A[], int B[], int D[]) {
    n = _n;
    forn(i, 0, n - 2) {
        g[A[i] + 1].eb(B[i] + 1, D[i]);
        g[B[i] + 1].eb(A[i] + 1, D[i]);
    }
    dfs(1, 0);
    forn(i, 1, C) {
        forn(j, 1, timer - (1 << i) + 1) {
            mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
        }
    }
}

ll Query(int S, int X[], int T, int Y[]) {
    if (S <= 20 && T <= 20) {
        ll res = ool;
        forn(i, 0, S - 1) {
            forn(j, 0, T - 1) {
                int v = X[i] + 1, u = Y[j] + 1;
                int lca = get(tin[u], tin[v]);
                res = min(res, lvl[u] + lvl[v] - 2 * lvl[lca]);
                if (!res) break;
            }
            if (!res) break;
        }
        return res;
    }
//    forn(i, 0, S - 1) cerr << X[i] <<  " ";
//    cerr << "\n";
//    forn(i, 0, T - 1) cerr << Y[i] << " ";
//    cerr << "\n";
    forn(i, 0, S - 1)
        tp1[X[i] + 1] = 1;
    forn(i, 0, T - 1)
        tp2[Y[i] + 1] = 1;
    ll res = dfs2(1, 0);
    forn(i, 0, S - 1)
        tp1[X[i] + 1] = 0;
    forn(i, 0, T - 1)
        tp2[Y[i] + 1] = 0;
    return res;
}

#ifdef krauch
#define MAX_N          500000
#define MAX_Q          100000
#define MAX_SUM_ST    1000000
#define MAX_VALUE  1000000000

int N, Q;
int A[MAX_N], B[MAX_N], D[MAX_N];
int S[MAX_N];
int T[MAX_N];
int X[MAX_SUM_ST];
int Y[MAX_SUM_ST];

int Qx[MAX_N];
int Qy[MAX_N];

int main() {
  freopen("sample-in-01.txt","r",stdin);

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

  if (2 != scanf("%d%d", &N, &Q)) {
    fprintf(stderr, "error: cannot read N and Q.\n");
    exit(1);
  }
  if (!(2 <= N && N <= 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 < N - 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] <= N - 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] <= N - 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] <= N - 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] <= N - 1)) {
        fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k);
        exit(1);
      }
    }
  }

  STop = 0;
  TTop = 0;
  Init(N, 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;
}
#endif

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