oj.uz

Submission #885854

# Submission time Handle Problem Language Result Execution time Memory
885854 2023-12-10T21:44:33 Z cegax Factories (JOI14_factories) C++17
100 / 100
 5351 ms 159008 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 5e5 + 10;
const int LOGN = 20;

vector<pair<int, int>> g[maxn];
ll best[maxn];
int sz[maxn], pi[maxn];
bool block[maxn];
int n;
int st[maxn], fin[maxn], timer = 0;
int up[maxn][LOGN];
ll h[maxn];

void dfs(int v, int p) {
    st[v] = timer++;

    up[v][0] = p;
    for(int i = 1; i < LOGN; i++) 
        up[v][i] = up[up[v][i-1]][i-1];

    for(auto [to, d] : g[v]) if(to != p) {
        h[to] = h[v] + d;
        dfs(to, v);
    }

    fin[v] = timer++;
}

bool is_parent(int u, int v) { return st[u] <= st[v] and fin[v] <= fin[u]; }

int lca(int u, int v) {
    if(is_parent(u, v)) return u;
    if(is_parent(v, u)) return v;

    for(int i = LOGN-1; i >= 0; i--) {
        if(!is_parent(up[u][i], v)) {
            u = up[u][i];
        }
    }
    return up[u][0];
}

ll dist(int u, int v) {
    int p = lca(u, v);
    return h[u] + h[v] - 2 * h[p];
}

int centroid(int v, int p, int n) {
  sz[v] = 1;
  int mx=0, cen=0;
  for (auto [u, d] : g[v]) if (u!=p && !block[u]) {
      cen ^= centroid(u, v, n);
      sz[v] += sz[u], mx=max(mx, sz[u]);
  }
  mx = max(mx, n-sz[v]);
  if (2*mx <= n) pi[cen=v]=p;
  return cen;
}

void decompose(int x, int p=-1, int m=n) {
  int cen = centroid(x, -1, m);
  if (~pi[cen]) sz[pi[cen]]=m-sz[cen];
  pi[cen]=p; block[cen]=1;
  for (auto [v, d] : g[cen]) if (!block[v]) {
      decompose(v, cen, sz[v]);
  }
}

const ll INF = (ll) 2e18;

void update(int v) {
  best[v] = 0;
  int u = v;
  while(pi[u] != -1) {
    u = pi[u];
    best[u] = min(best[u], dist(v, u));
  }
}

void clean(int v) {
  do {
    best[v] = INF;
    v = pi[v];
  }while(v != -1);
}

ll query(int v) {
    ll ans = best[v];
    int u = v;
    while(pi[u] != -1) {
        u = pi[u];
        ans = min(ans, best[u] + dist(u, v));
    }
    return ans;
}

void Init(int N, int a[], int b[], int d[]) {
	n = N;
	for(int i = 0; i < n-1; i++) {
		int u = a[i], v = b[i];
		g[u].push_back({v, d[i]});
		g[v].push_back({u, d[i]});
	}

	for(int i = 0; i < n; i++) best[i] = INF;

    decompose(0);
    dfs(0, 0);
}

ll Query(int s, int x[], int t, int y[]) {
	for(int i = 0; i < s; i++) update(x[i]);

	ll ans = INF;

	for(int j = 0; j < t; j++) ans = min(ans, query(y[j]));

	for(int i = 0; i < s; i++) clean(x[i]);

	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 41308 KB Output is correct
2 Correct 441 ms 57432 KB Output is correct
3 Correct 920 ms 57440 KB Output is correct
4 Correct 924 ms 57424 KB Output is correct
5 Correct 456 ms 57680 KB Output is correct
6 Correct 150 ms 57316 KB Output is correct
7 Correct 904 ms 57428 KB Output is correct
8 Correct 968 ms 57384 KB Output is correct
9 Correct 446 ms 57820 KB Output is correct
10 Correct 149 ms 57172 KB Output is correct
11 Correct 908 ms 57388 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 41304 KB Output is correct
2 Correct 1535 ms 128196 KB Output is correct
3 Correct 3100 ms 131200 KB Output is correct
4 Correct 469 ms 128376 KB Output is correct
5 Correct 1987 ms 159008 KB Output is correct
6 Correct 3108 ms 131904 KB Output is correct
7 Correct 2178 ms 77132 KB Output is correct
8 Correct 229 ms 76992 KB Output is correct
9 Correct 945 ms 80536 KB Output is correct
10 Correct 2161 ms 77904 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 41308 KB Output is correct
2 Correct 441 ms 57432 KB Output is correct
3 Correct 920 ms 57440 KB Output is correct
4 Correct 924 ms 57424 KB Output is correct
5 Correct 456 ms 57680 KB Output is correct
6 Correct 150 ms 57316 KB Output is correct
7 Correct 904 ms 57428 KB Output is correct
8 Correct 968 ms 57384 KB Output is correct
9 Correct 446 ms 57820 KB Output is correct
10 Correct 149 ms 57172 KB Output is correct
11 Correct 908 ms 57388 KB Output is correct
12 Correct 7 ms 41304 KB Output is correct
13 Correct 1535 ms 128196 KB Output is correct
14 Correct 3100 ms 131200 KB Output is correct
15 Correct 469 ms 128376 KB Output is correct
16 Correct 1987 ms 159008 KB Output is correct
17 Correct 3108 ms 131904 KB Output is correct
18 Correct 2178 ms 77132 KB Output is correct
19 Correct 229 ms 76992 KB Output is correct
20 Correct 945 ms 80536 KB Output is correct
21 Correct 2161 ms 77904 KB Output is correct
22 Correct 1937 ms 132740 KB Output is correct
23 Correct 2106 ms 134296 KB Output is correct
24 Correct 5005 ms 135772 KB Output is correct
25 Correct 4726 ms 138116 KB Output is correct
26 Correct 4674 ms 136244 KB Output is correct
27 Correct 2469 ms 157696 KB Output is correct
28 Correct 521 ms 134840 KB Output is correct
29 Correct 4816 ms 135824 KB Output is correct
30 Correct 4869 ms 135192 KB Output is correct
31 Correct 5351 ms 135724 KB Output is correct
32 Correct 939 ms 81292 KB Output is correct
33 Correct 225 ms 76996 KB Output is correct
34 Correct 889 ms 75600 KB Output is correct
35 Correct 932 ms 75824 KB Output is correct
36 Correct 2176 ms 76352 KB Output is correct
37 Correct 2227 ms 76192 KB Output is correct