Submission #305897

# Submission time Handle Problem Language Result Execution time Memory
305897 2020-09-24T04:35:22 Z limabeans Factories (JOI14_factories) C++17
15 / 100
8000 ms 134892 KB
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll inf = 1e18;
const int maxn = 5e5 + 100;
const int LOG = 20;

int n;
vector<pair<ll,int>> g[maxn];
int par[LOG+1][maxn];
int dep[maxn];
ll len[maxn];

void dfs(int at, int p) {
    for (int j=1; j<LOG; j++) {
	par[j][at] = par[j-1][par[j-1][at]];
    }
    for (auto ed: g[at]) {
	ll wei = ed.first;
	int to = ed.second;
	if (to == p) continue;
	dep[to] = 1+dep[at];
	len[to] = len[at] + wei;
	par[0][to] = at;
	dfs(to, at);
    }
}




int lca(int u, int v) {
    if (dep[u]<dep[v]) swap(u, v);
    int dx = dep[u]-dep[v];
    for (int j=0; j<LOG; j++) {
	if (dx>>j&1) {
	    u = par[j][u];
	}
    }

    if (u == v) return u;

    for (int j=LOG-1; j>=0; j--) {
	if (par[j][u] != par[j][v]) {
	    u = par[j][u];
	    v = par[j][v];
	}
    }

    return par[0][u];
}


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


vector<int> ctree[maxn];
bool bad[maxn];
int siz[maxn];

int findCenter(int at) {
    function<void(int,int)> dfs = [&](int at, int p) {
	siz[at] = 1;
	for (auto ed: g[at]) {
	    int to = ed.second;
	    if (!bad[to] && to != p) {
		dfs(to, at);
		siz[at] += siz[to];
	    }
	}
    };

    dfs(at, -1);
    int all = siz[at];
    bool ok = true;
    while (ok) {
	ok = false;
	for (auto ed: g[at]) {
	    int to = ed.second;
	    if (bad[to]) continue;
	    if (siz[to] > siz[at]) continue;
	    if (siz[to]*2 >= all) {
		at = to;
		ok = true;
		break;
	    }
	}
    }

    return at;
}

int build(int at) {
    at = findCenter(at);
    bad[at] = true;
    for (auto ed: g[at]) {
	int to = ed.second;
	if (!bad[to]) {
	    int nc = build(to);
	    ctree[at].push_back(nc);
	    ctree[nc].push_back(at);
	}
    }
    return at;
}

int cpar[maxn];

void cdfs(int at, int p, int dep=0) {
    assert(dep <= 23);
    for (int to: ctree[at]) {
	if (to == p) continue;
	cpar[to] = at;
	cdfs(to, at, dep+1);
    }
}


ll nearest[maxn];

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

    dfs(0, -1);
    int root = build(0);
    cpar[root] = -1;
    cdfs(root, -1);

    for (int i=0; i<n+10; i++) {
	nearest[i] = inf;
    }
}



long long Query(int S, int X[], int T, int Y[]) {
    ll res = inf;
    set<int> v;
    
    for (int i=0; i<S; i++) {
	int node = X[i];
	int at = node;
	while (~at) {
	    v.insert(at);
	    nearest[at] = min(nearest[at], dist(node, at));
	    at = cpar[at];
	}
    }


    for (int i=0; i<T; i++) {
	int node = Y[i];
	int at = node;
	while (~at) {
	    v.insert(at);
	    ll cur = nearest[at] + dist(node, at);
	    res = min(res, cur);
	    at = cpar[at];
	}
    }

    for (int x: v) {
	nearest[x] = inf;
    }
    
    return res;
}
# Verdict Execution time Memory Grader output
1 Correct 65 ms 24440 KB Output is correct
2 Correct 2924 ms 33144 KB Output is correct
3 Correct 4269 ms 33144 KB Output is correct
4 Correct 4442 ms 33396 KB Output is correct
5 Correct 4946 ms 33708 KB Output is correct
6 Correct 940 ms 33144 KB Output is correct
7 Correct 4242 ms 33400 KB Output is correct
8 Correct 4691 ms 33392 KB Output is correct
9 Correct 5220 ms 33588 KB Output is correct
10 Correct 936 ms 33144 KB Output is correct
11 Correct 4188 ms 33400 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 23 ms 24192 KB Output is correct
2 Correct 7646 ms 132144 KB Output is correct
3 Execution timed out 8092 ms 134892 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 65 ms 24440 KB Output is correct
2 Correct 2924 ms 33144 KB Output is correct
3 Correct 4269 ms 33144 KB Output is correct
4 Correct 4442 ms 33396 KB Output is correct
5 Correct 4946 ms 33708 KB Output is correct
6 Correct 940 ms 33144 KB Output is correct
7 Correct 4242 ms 33400 KB Output is correct
8 Correct 4691 ms 33392 KB Output is correct
9 Correct 5220 ms 33588 KB Output is correct
10 Correct 936 ms 33144 KB Output is correct
11 Correct 4188 ms 33400 KB Output is correct
12 Correct 23 ms 24192 KB Output is correct
13 Correct 7646 ms 132144 KB Output is correct
14 Execution timed out 8092 ms 134892 KB Time limit exceeded
15 Halted 0 ms 0 KB -