Submission #499061

#	Time	Username	Problem	Language	Result	Execution time	Memory
499061		600Mihnea	Factories (JOI14_factories)	C++17	100 / 100	2512 ms	280712 KiB

factories

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

using namespace std;

typedef long long ll;
const int N = (int) 5e5 + 7;
const int K = 21;
int n;
int indexOfNode[N];
int currentIndex;
int secondCurrentIndex;
int dep[N];
int first[N];
int last[N];
int lg[2 * N];
vector<pair<int, int>> g[N];
pair<int, int> rmq[K][2 * N];
ll sum[N];

void addEdgeToGraph(int a, int b, int d) {
  g[a].push_back({b, d});
  g[b].push_back({a, d});
}

void build_stuff(int a, int p = 0) {
  indexOfNode[a] = ++currentIndex;
  rmq[0][++secondCurrentIndex] = {dep[a], a};
  first[a] = secondCurrentIndex;
  for (auto &it : g[a]) {
    int b = it.first;
    int cost = it.second;
    if (b != p) {
      dep[b] = 1 + dep[a];
      sum[b] = cost + sum[a];
      build_stuff(b, a);
      rmq[0][++secondCurrentIndex] = {dep[a], a};
    }
  }
  last[a] = secondCurrentIndex;
}

int getlca(int a, int b) {
  if (first[a] > last[b]) {
    swap(a, b);
  }
  a = first[a];
  b = last[b];
  int k = lg[b - a + 1];
  return min(rmq[k][a], rmq[k][b - (1 << k) + 1]).second;
}

void Init(int nn, int edges_a[], int edges_b[], int edges_d[]) {
  n = nn;
  for (int i = 1; i <= n; i++) {
    g[i].clear();
  }
  for (int i = 0; i < n - 1; i++) {
    addEdgeToGraph(edges_a[i] + 1, edges_b[i] + 1, edges_d[i]);
  }
  build_stuff(1);
  for (int i = 2; i <= secondCurrentIndex; i++) {
    lg[i] = 1 + lg[i / 2];
  }
  for (int k = 1; (1 << k) <= secondCurrentIndex; k++) {
    for (int i = 1; i + (1 << k) - 1 <= secondCurrentIndex; i++) {
      rmq[k][i] = min(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
    }
  }
}

int valueOf[N], par[N], root;
vector<pair<int, ll>> secondg[N];

const ll INF = (ll) 1e18 + 7;

ll best;
ll mn1[N];
ll mn2[N];

void dfs(int a) {
  mn1[a] = mn2[a] = INF;
  if (valueOf[a] == 1) {
    mn1[a] = 0;
  }
  if (valueOf[a] == 2) {
    mn2[a] = 0;
  }
  for (auto &it : secondg[a]) {
    int b = it.first;
    ll c = it.second;
    dfs(b);
    mn1[a] = min(mn1[a], mn1[b] + c);
    mn2[a] = min(mn2[a], mn2[b] + c);
  }
  best = min(best, mn1[a] + mn2[a]);
}


long long Query(int s, int x[], int t, int y[]) {
  vector<pair<int, int>> guys;
  for (int i = 0; i < s; i++) {
    guys.push_back({indexOfNode[x[i] + 1], x[i] + 1});
    valueOf[x[i] + 1] = 1;
  }
  for (int i = 0; i < t; i++) {
    guys.push_back({indexOfNode[y[i] + 1], y[i] + 1});
    valueOf[y[i] + 1] = 2;
  }

  sort(guys.begin(), guys.end());

  vector<pair<int, int>> secondGuys = guys;
  for (int i = 1; i < (int) guys.size(); i++) {
    int node = getlca(guys[i - 1].second, guys[i].second);
    secondGuys.push_back({indexOfNode[node], node});
  }
  sort(secondGuys.begin(), secondGuys.end());


  vector<int> path;

  root = secondGuys[0].second;
  par[root] = 0;
  path.push_back(root);


  for (int it = 1; it < (int) secondGuys.size(); it++) {
    if (secondGuys[it] == secondGuys[it - 1]) {
      continue;
    }
    int node = secondGuys[it].second;
    while (1) {
      int lca = getlca(node, path.back());
      if (lca != path.back()) {
        path.pop_back();
      } else {
        break;
      }
    }
    par[node] = path.back();
    path.push_back(node);
  }

  for (int ite = 1; ite < (int) secondGuys.size(); ite++) {
    if (secondGuys[ite] == secondGuys[ite - 1]) {
      continue;
    }
    auto &it = secondGuys[ite];
    int x1 = par[it.second];
    int x2 = it.second;
    secondg[par[it.second]].push_back({it.second, sum[it.second] - sum[par[it.second]]});
  }

  best = INF;
  dfs(root);
  for (auto &it : secondGuys) {
    valueOf[it.second] = 0;
    par[it.second] = 0;
    secondg[it.second].clear();
  }
  return best;
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:150:9: warning: unused variable 'x1' [-Wunused-variable]
  150 |     int x1 = par[it.second];
      |         ^~
factories.cpp:151:9: warning: unused variable 'x2' [-Wunused-variable]
  151 |     int x2 = it.second;
      |         ^~

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