Submission #885840

#	Time	Username	Problem	Language	Result	Execution time	Memory
885840		cegax	Factories (JOI14_factories)	C++17	0 / 100	8025 ms	25176 KiB

factories

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e5 + 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, ll d=0) {
    best[v] = d;
    if(pi[v] != -1) update(pi[v], d + dist(v, pi[v]));
}

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

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

void Init(int n, int a[], int b[], int d[]) {
	for(int i = 0; i < n; 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: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67