oj.uz

Submission #258616

# Submission time Handle Problem Language Result Execution time Memory
258616 2020-08-06T08:54:01 Z fedoseevtimofey Factories (JOI14_factories) C++14
100 / 100
 6789 ms 140724 KB 
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

#include "factories.h"

const int N = 5e5 + 7;
const int K = 20;
vector <pair <int, int>> g[N];
int go[K][N];
ll h[N];
int tin[N], tout[N];
int id[N];

int timer = 0;

int n;

void dfs(int u, int p) {
  tin[u] = timer++;
  go[0][u] = p;
  for (int i = 1; i < K; ++i) {
    go[i][u] = go[i - 1][go[i - 1][u]];
  }
  for (auto pr : g[u]) {
    int v = pr.first, w = pr.second;
    if (v != p) {
      h[v] = h[u] + w;
      dfs(v, u);
    }
  } 
  tout[u] = timer++;
}

bool anc(int a, int b) {
  return tin[a] <= tin[b] && tout[b] <= tout[a];
}

int lca(int a, int b) {
  if (anc(a, b)) return a;
  for (int i = K - 1; i >= 0; --i) {
    if (!anc(go[i][a], b)) {
      a = go[i][a];
    }
  }
  return go[0][a];
}

ll dist(int a, int b) {
  return h[a] + h[b] - 2 * h[lca(a, b)];
}
  
void Init(int N, int A[], int B[], int D[]) {
  n = N;
  for (int i = 0; i + 1 < n; ++i) {
    g[A[i]].push_back({B[i], D[i]});
    g[B[i]].push_back({A[i], D[i]});
  }
  dfs(0, 0);
} 

long long Query(int s, int X[], int t, int Y[]) {
  vector <int> vr;
  for (int i = 0; i < s; ++i) vr.push_back(X[i]);
  for (int i = 0; i < t; ++i) vr.push_back(Y[i]);
  sort(vr.begin(), vr.end(), [&] (int a, int b) {
    return tin[a] < tin[b];
  });
  {
    vector <int> nvr;
    for (int i = 0; i < (int)vr.size(); ++i) {
      int j = (i + 1) % (int)vr.size();
      nvr.push_back(lca(vr[i], vr[j]));
    }
    for (int x : vr) nvr.push_back(x);
    vr = nvr;
    sort(vr.begin(), vr.end());
    vr.resize(unique(vr.begin(), vr.end()) - vr.begin());
    sort(vr.begin(), vr.end(), [&] (int a, int b) {
      return tin[a] < tin[b];
    });
  }
  int k = vr.size();
  for (int i = 0; i < k; ++i) id[vr[i]] = i;
  vector <vector <pair <int, ll>>> ng(k);
  vector <int> st;
  for (int i = 0; i < k; ++i) {
    while (!st.empty() && !anc(st.back(), vr[i])) {
      st.pop_back();
    }
    if (!st.empty()) {
      ng[id[st.back()]].push_back({id[vr[i]], dist(st.back(), vr[i])});
      ng[id[vr[i]]].push_back({id[st.back()], dist(st.back(), vr[i])});
    }
    st.push_back(vr[i]);
  }
  vector <int> tp(k, -1);
  for (int i = 0; i < s; ++i) {
    tp[id[X[i]]] = 0;
  }
  for (int i = 0; i < t; ++i) {
    tp[id[Y[i]]] = 1;
  }
  const ll Inf = 1e18;
  vector <ll> dp(k, Inf);
  vector <ll> sdp(k, Inf);
  function <void(int, int)> jhfs = [&] (int u, int p) {
    if (tp[u] == 0) dp[u] = 0;
    for (auto pr : ng[u]) {
      int v = pr.first; ll w = pr.second;
      if (v != p) {
        jhfs(v, u);
        ll x = dp[v] + w;
        if (x < dp[u]) {
          swap(x, dp[u]);
        }
        if (x < sdp[u]) {
          swap(x, sdp[u]);
        }
      }
    }
  };    
  jhfs(0, 0);
  vector <ll> dpU(k, Inf);

  function <void(int, int, ll)> zhfs = [&] (int u, int p, ll best) {
    if (tp[u] == 0) best = 0;
    dpU[u] = best;
    for (auto pr : ng[u]) {
      int v = pr.first; ll w = pr.second;
      if (v != p) {
        ll go = best + w;
        if (dp[v] + w != dp[u]) {
          go = min(go, dp[u] + w);
        } else {
          go = min(go, sdp[u] + w);
        }
        zhfs(v, u, go);
      }
    }
  };    
  zhfs(0, 0, Inf);
  ll ans = Inf;
  for (int i = 0; i < k; ++i) {
    if (tp[i] == 1) {
      ans = min(ans, dp[i]);
      ans = min(ans, dpU[i]);
    }
  }
  return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 12800 KB Output is correct
2 Correct 1729 ms 30800 KB Output is correct
3 Correct 1773 ms 30584 KB Output is correct
4 Correct 1670 ms 31244 KB Output is correct
5 Correct 1207 ms 31372 KB Output is correct
6 Correct 1334 ms 30780 KB Output is correct
7 Correct 1751 ms 30584 KB Output is correct
8 Correct 1673 ms 31128 KB Output is correct
9 Correct 1215 ms 31276 KB Output is correct
10 Correct 1481 ms 30972 KB Output is correct
11 Correct 1749 ms 30712 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12416 KB Output is correct
2 Correct 3752 ms 111332 KB Output is correct
3 Correct 3948 ms 111296 KB Output is correct
4 Correct 3310 ms 111560 KB Output is correct
5 Correct 2086 ms 128696 KB Output is correct
6 Correct 4243 ms 113328 KB Output is correct
7 Correct 3855 ms 50504 KB Output is correct
8 Correct 3045 ms 51436 KB Output is correct
9 Correct 1503 ms 53500 KB Output is correct
10 Correct 3971 ms 51836 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 12800 KB Output is correct
2 Correct 1729 ms 30800 KB Output is correct
3 Correct 1773 ms 30584 KB Output is correct
4 Correct 1670 ms 31244 KB Output is correct
5 Correct 1207 ms 31372 KB Output is correct
6 Correct 1334 ms 30780 KB Output is correct
7 Correct 1751 ms 30584 KB Output is correct
8 Correct 1673 ms 31128 KB Output is correct
9 Correct 1215 ms 31276 KB Output is correct
10 Correct 1481 ms 30972 KB Output is correct
11 Correct 1749 ms 30712 KB Output is correct
12 Correct 12 ms 12416 KB Output is correct
13 Correct 3752 ms 111332 KB Output is correct
14 Correct 3948 ms 111296 KB Output is correct
15 Correct 3310 ms 111560 KB Output is correct
16 Correct 2086 ms 128696 KB Output is correct
17 Correct 4243 ms 113328 KB Output is correct
18 Correct 3855 ms 50504 KB Output is correct
19 Correct 3045 ms 51436 KB Output is correct
20 Correct 1503 ms 53500 KB Output is correct
21 Correct 3971 ms 51836 KB Output is correct
22 Correct 5743 ms 130396 KB Output is correct
23 Correct 5815 ms 132640 KB Output is correct
24 Correct 5773 ms 133128 KB Output is correct
25 Correct 6271 ms 135240 KB Output is correct
26 Correct 6789 ms 120332 KB Output is correct
27 Correct 3356 ms 140724 KB Output is correct
28 Correct 5610 ms 130508 KB Output is correct
29 Correct 6625 ms 119696 KB Output is correct
30 Correct 6525 ms 119072 KB Output is correct
31 Correct 6705 ms 119544 KB Output is correct
32 Correct 1826 ms 63876 KB Output is correct
33 Correct 3069 ms 59912 KB Output is correct
34 Correct 3820 ms 49128 KB Output is correct
35 Correct 3654 ms 48992 KB Output is correct
36 Correct 3838 ms 49444 KB Output is correct
37 Correct 3837 ms 49320 KB Output is correct