oj.uz

Submission #305902

# Submission time Handle Problem Language Result Execution time Memory
305902 2020-09-24T04:42:30 Z limabeans Factories (JOI14_factories) C++17
15 / 100
 8000 ms 128816 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];

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

int findCenter(int at) {
 

    dfs2(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);
    }
}



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);

}



long long Query(int S, int X[], int T, int Y[]) {
    ll res = inf;
    map<int,ll> nearest;
    
    for (int i=0; i<S; i++) {
	int node = X[i];
	int at = node;
	int iter=0;
	while (~at) {
	    if (!nearest.count(at)) nearest[at] = inf;
	    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) {
	    ll cur = (nearest.count(at) ? nearest[at] : inf) + dist(node, at);
	    res = min(res, cur);
	    at = cpar[at];
	    assert(++iter <= 23);
	}
    }
    
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 24320 KB Output is correct
2 Correct 3286 ms 33276 KB Output is correct
3 Correct 4936 ms 33244 KB Output is correct
4 Correct 4275 ms 33420 KB Output is correct
5 Correct 5873 ms 33400 KB Output is correct
6 Correct 903 ms 33144 KB Output is correct
7 Correct 4887 ms 33044 KB Output is correct
8 Correct 4996 ms 33104 KB Output is correct
9 Correct 5784 ms 33400 KB Output is correct
10 Correct 914 ms 33300 KB Output is correct
11 Correct 4926 ms 33392 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24192 KB Output is correct
2 Correct 6873 ms 128140 KB Output is correct
3 Execution timed out 8099 ms 128816 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 24320 KB Output is correct
2 Correct 3286 ms 33276 KB Output is correct
3 Correct 4936 ms 33244 KB Output is correct
4 Correct 4275 ms 33420 KB Output is correct
5 Correct 5873 ms 33400 KB Output is correct
6 Correct 903 ms 33144 KB Output is correct
7 Correct 4887 ms 33044 KB Output is correct
8 Correct 4996 ms 33104 KB Output is correct
9 Correct 5784 ms 33400 KB Output is correct
10 Correct 914 ms 33300 KB Output is correct
11 Correct 4926 ms 33392 KB Output is correct
12 Correct 22 ms 24192 KB Output is correct
13 Correct 6873 ms 128140 KB Output is correct
14 Execution timed out 8099 ms 128816 KB Time limit exceeded
15 Halted 0 ms 0 KB -