Submission #305894

# Submission time Handle Problem Language Result Execution time Memory
305894 2020-09-24T04:30:50 Z limabeans Factories (JOI14_factories) C++17
15 / 100
8000 ms 134536 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) {
    for (int to: ctree[at]) {
	if (to == p) continue;
	cpar[to] = at;
	cdfs(to, at);
    }
}


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;
    vector<int> v;
    
    for (int i=0; i<S; i++) {
	int node = X[i];
	int at = node;
	while (~at) {
	    v.push_back(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.push_back(at);
	    ll cur = nearest[at] + dist(node, at);
	    res = min(res, cur);
	    at = cpar[at];
	}
    }

    while (v.size()) {
	nearest[v.back()] = inf;
	v.pop_back();
    }
    
    return res;
}


# Verdict Execution time Memory Grader output
1 Correct 44 ms 24440 KB Output is correct
2 Correct 1405 ms 33332 KB Output is correct
3 Correct 2287 ms 42684 KB Output is correct
4 Correct 2263 ms 42944 KB Output is correct
5 Correct 2440 ms 43428 KB Output is correct
6 Correct 523 ms 42616 KB Output is correct
7 Correct 2280 ms 42616 KB Output is correct
8 Correct 2401 ms 43288 KB Output is correct
9 Correct 2438 ms 43468 KB Output is correct
10 Correct 529 ms 42636 KB Output is correct
11 Correct 2231 ms 42488 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 24 ms 24192 KB Output is correct
2 Correct 6595 ms 132016 KB Output is correct
3 Execution timed out 8087 ms 134536 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 44 ms 24440 KB Output is correct
2 Correct 1405 ms 33332 KB Output is correct
3 Correct 2287 ms 42684 KB Output is correct
4 Correct 2263 ms 42944 KB Output is correct
5 Correct 2440 ms 43428 KB Output is correct
6 Correct 523 ms 42616 KB Output is correct
7 Correct 2280 ms 42616 KB Output is correct
8 Correct 2401 ms 43288 KB Output is correct
9 Correct 2438 ms 43468 KB Output is correct
10 Correct 529 ms 42636 KB Output is correct
11 Correct 2231 ms 42488 KB Output is correct
12 Correct 24 ms 24192 KB Output is correct
13 Correct 6595 ms 132016 KB Output is correct
14 Execution timed out 8087 ms 134536 KB Time limit exceeded
15 Halted 0 ms 0 KB -