oj.uz

Submission #305899

# Submission time Handle Problem Language Result Execution time Memory
305899 2020-09-24T04:39:31 Z limabeans Factories (JOI14_factories) C++17
15 / 100
 8000 ms 134864 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;
	int iter=0;
	while (~at) {
	    v.insert(at);
	    nearest[at] = min(nearest[at], dist(node, at));
	    at = cpar[at];
	    assert(++iter <= 23);
	}
    }


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

    for (int x: v) {
	nearest[x] = inf;
    }
    
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 24444 KB Output is correct
2 Correct 2884 ms 33452 KB Output is correct
3 Correct 4314 ms 33400 KB Output is correct
4 Correct 4396 ms 33656 KB Output is correct
5 Correct 4935 ms 33664 KB Output is correct
6 Correct 914 ms 33396 KB Output is correct
7 Correct 4133 ms 33336 KB Output is correct
8 Correct 4568 ms 33556 KB Output is correct
9 Correct 4885 ms 33836 KB Output is correct
10 Correct 914 ms 33528 KB Output is correct
11 Correct 4164 ms 33184 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24192 KB Output is correct
2 Correct 7561 ms 132316 KB Output is correct
3 Execution timed out 8067 ms 134864 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 24444 KB Output is correct
2 Correct 2884 ms 33452 KB Output is correct
3 Correct 4314 ms 33400 KB Output is correct
4 Correct 4396 ms 33656 KB Output is correct
5 Correct 4935 ms 33664 KB Output is correct
6 Correct 914 ms 33396 KB Output is correct
7 Correct 4133 ms 33336 KB Output is correct
8 Correct 4568 ms 33556 KB Output is correct
9 Correct 4885 ms 33836 KB Output is correct
10 Correct 914 ms 33528 KB Output is correct
11 Correct 4164 ms 33184 KB Output is correct
12 Correct 25 ms 24192 KB Output is correct
13 Correct 7561 ms 132316 KB Output is correct
14 Execution timed out 8067 ms 134864 KB Time limit exceeded
15 Halted 0 ms 0 KB -