oj.uz

Submission #305901

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


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 62 ms 24448 KB Output is correct
2 Correct 2836 ms 33292 KB Output is correct
3 Correct 4214 ms 33416 KB Output is correct
4 Correct 4358 ms 33528 KB Output is correct
5 Correct 4831 ms 33808 KB Output is correct
6 Correct 853 ms 33528 KB Output is correct
7 Correct 4101 ms 33328 KB Output is correct
8 Correct 4474 ms 33696 KB Output is correct
9 Correct 4794 ms 33572 KB Output is correct
10 Correct 848 ms 33280 KB Output is correct
11 Correct 4096 ms 33512 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 7344 ms 132440 KB Output is correct
3 Execution timed out 8038 ms 133048 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 24448 KB Output is correct
2 Correct 2836 ms 33292 KB Output is correct
3 Correct 4214 ms 33416 KB Output is correct
4 Correct 4358 ms 33528 KB Output is correct
5 Correct 4831 ms 33808 KB Output is correct
6 Correct 853 ms 33528 KB Output is correct
7 Correct 4101 ms 33328 KB Output is correct
8 Correct 4474 ms 33696 KB Output is correct
9 Correct 4794 ms 33572 KB Output is correct
10 Correct 848 ms 33280 KB Output is correct
11 Correct 4096 ms 33512 KB Output is correct
12 Correct 22 ms 24192 KB Output is correct
13 Correct 7344 ms 132440 KB Output is correct
14 Execution timed out 8038 ms 133048 KB Time limit exceeded
15 Halted 0 ms 0 KB -