oj.uz

Submission #306115

# Submission time Handle Problem Language Result Execution time Memory
306115 2020-09-24T14:31:13 Z limabeans Factories (JOI14_factories) C++17
100 / 100
 7023 ms 523164 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


struct sparse_table {
 
    int LOG = 0;
    int n;
    vector<pair<int,int>> a[100];
    vector<int> lg_floor;
 
    pair<int,int> eval(pair<int,int> x, pair<int,int> y) {
	return min(x, y);
    }
 
    void init(vector<pair<int,int>> v) {
	n = v.size();
	LOG = 0;
	while ((1<<LOG) <= n) LOG++;
	lg_floor.resize(n+10);
	lg_floor[1] = 0;
	for (int i=2; i<n+10; i++) lg_floor[i] = 1 + lg_floor[i/2];
	for (int j=0; j<LOG; j++) a[j].resize(n);
	for (int i=0; i<n; i++) a[0][i] = v[i];
	
 
	for (int j=1; j<LOG; j++) {
	    for (int i=0; i<n; i++) {
		a[j][i] = a[j-1][i];
		if (i + (1<<(j-1)) < n) {
		    a[j][i] = eval(a[j][i], a[j-1][i + (1<<(j-1))]);
		}
	    }
	}
    }
 
    pair<int,int> get(int l, int r) {
	assert(l<=r);
	int lg = lg_floor[r - l + 1];
 
	return eval(a[lg][l], a[lg][r-(1<<lg)+1]);
	
    }
};


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

int cloc = 0;
int tin[maxn];
vector<pair<int,int>> ett;

sparse_table tbl;

void dfs(int at, int p) {
    tin[at] = cloc++;
    ett.push_back({tin[at], at});
    
    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);
	ett.push_back({tin[at], at});
	cloc++;
    }

    ett.push_back({tin[at], at});
    cloc++;
}


int lca(int u, int v) {
    if (u==v) return u;
    int lo = tin[u];
    int hi = tin[v];
    if (lo>hi) swap(lo, hi);
    pair<int,int> res = tbl.get(lo, hi);
    return res.second;
}


int lcaBrute(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];
int cdep[maxn];
ll up[25][maxn];

void cdfs(int at, int p, int dep=0) {
    assert(dep <= 23);
    for (int i=0,x=at; i<=dep; i++, x = cpar[x]) {
	up[i][at]=dist(at, x);
    }
    for (int to: ctree[at]) {
	if (to == p) continue;
	cpar[to] = at;
	cdep[to] = 1+cdep[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);
    tbl.init(ett);
    
    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;
    for (int i=0; i<S; i++) {
	int node = X[i];
	int at = node;
	int j = 0;
	int iter=0;
	while (~at) {
	    nearest[at] = min(nearest[at], up[j++][node]);
	    at = cpar[at];
	    assert(++iter <= 23);
	}
    }


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

     for (int i=0; i<S; i++) {
	int node = X[i];
	int at = node;
	int iter=0;
	while (~at) {
	    nearest[at] = inf;
	    at = cpar[at];
	    assert(++iter <= 23);
	}
    }

    
    
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24832 KB Output is correct
2 Correct 420 ms 36964 KB Output is correct
3 Correct 452 ms 37116 KB Output is correct
4 Correct 446 ms 37164 KB Output is correct
5 Correct 481 ms 37368 KB Output is correct
6 Correct 338 ms 36488 KB Output is correct
7 Correct 448 ms 36984 KB Output is correct
8 Correct 453 ms 37244 KB Output is correct
9 Correct 469 ms 37456 KB Output is correct
10 Correct 334 ms 36472 KB Output is correct
11 Correct 447 ms 36984 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24444 KB Output is correct
2 Correct 3651 ms 477800 KB Output is correct
3 Correct 4659 ms 475992 KB Output is correct
4 Correct 2121 ms 407012 KB Output is correct
5 Correct 6056 ms 500220 KB Output is correct
6 Correct 4819 ms 477560 KB Output is correct
7 Correct 1552 ms 117892 KB Output is correct
8 Correct 702 ms 118912 KB Output is correct
9 Correct 1721 ms 134268 KB Output is correct
10 Correct 1613 ms 131540 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24832 KB Output is correct
2 Correct 420 ms 36964 KB Output is correct
3 Correct 452 ms 37116 KB Output is correct
4 Correct 446 ms 37164 KB Output is correct
5 Correct 481 ms 37368 KB Output is correct
6 Correct 338 ms 36488 KB Output is correct
7 Correct 448 ms 36984 KB Output is correct
8 Correct 453 ms 37244 KB Output is correct
9 Correct 469 ms 37456 KB Output is correct
10 Correct 334 ms 36472 KB Output is correct
11 Correct 447 ms 36984 KB Output is correct
12 Correct 20 ms 24444 KB Output is correct
13 Correct 3651 ms 477800 KB Output is correct
14 Correct 4659 ms 475992 KB Output is correct
15 Correct 2121 ms 407012 KB Output is correct
16 Correct 6056 ms 500220 KB Output is correct
17 Correct 4819 ms 477560 KB Output is correct
18 Correct 1552 ms 117892 KB Output is correct
19 Correct 702 ms 118912 KB Output is correct
20 Correct 1721 ms 134268 KB Output is correct
21 Correct 1613 ms 131540 KB Output is correct
22 Correct 4422 ms 464220 KB Output is correct
23 Correct 4463 ms 475796 KB Output is correct
24 Correct 5793 ms 482744 KB Output is correct
25 Correct 5811 ms 506304 KB Output is correct
26 Correct 5761 ms 502544 KB Output is correct
27 Correct 7023 ms 523164 KB Output is correct
28 Correct 2332 ms 435924 KB Output is correct
29 Correct 5767 ms 502304 KB Output is correct
30 Correct 5787 ms 501540 KB Output is correct
31 Correct 5618 ms 502208 KB Output is correct
32 Correct 1747 ms 135224 KB Output is correct
33 Correct 705 ms 119604 KB Output is correct
34 Correct 1203 ms 125456 KB Output is correct
35 Correct 1218 ms 125556 KB Output is correct
36 Correct 1519 ms 128428 KB Output is correct
37 Correct 1532 ms 128796 KB Output is correct