oj.uz

Submission #305895

# Submission time Handle Problem Language Result Execution time Memory
305895 2020-09-24T04:32:33 Z limabeans Factories (JOI14_factories) C++17
15 / 100
 8000 ms 134800 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;
    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;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 24448 KB Output is correct
2 Correct 1369 ms 33320 KB Output is correct
3 Correct 2243 ms 33280 KB Output is correct
4 Correct 2239 ms 33716 KB Output is correct
5 Correct 2386 ms 34220 KB Output is correct
6 Correct 496 ms 33144 KB Output is correct
7 Correct 2233 ms 33156 KB Output is correct
8 Correct 2320 ms 33668 KB Output is correct
9 Correct 2374 ms 34136 KB Output is correct
10 Correct 505 ms 33144 KB Output is correct
11 Correct 2215 ms 33144 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24320 KB Output is correct
2 Correct 6290 ms 131940 KB Output is correct
3 Execution timed out 8077 ms 134800 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 24448 KB Output is correct
2 Correct 1369 ms 33320 KB Output is correct
3 Correct 2243 ms 33280 KB Output is correct
4 Correct 2239 ms 33716 KB Output is correct
5 Correct 2386 ms 34220 KB Output is correct
6 Correct 496 ms 33144 KB Output is correct
7 Correct 2233 ms 33156 KB Output is correct
8 Correct 2320 ms 33668 KB Output is correct
9 Correct 2374 ms 34136 KB Output is correct
10 Correct 505 ms 33144 KB Output is correct
11 Correct 2215 ms 33144 KB Output is correct
12 Correct 20 ms 24320 KB Output is correct
13 Correct 6290 ms 131940 KB Output is correct
14 Execution timed out 8077 ms 134800 KB Time limit exceeded
15 Halted 0 ms 0 KB -