oj.uz

Submission #305907

# Submission time Handle Problem Language Result Execution time Memory
305907 2020-09-24T05:05:08 Z limabeans Factories (JOI14_factories) C++17
15 / 100
 8000 ms 395372 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];

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);
    tbl.init(ett);
    
    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 64 ms 24576 KB Output is correct
2 Correct 2755 ms 35228 KB Output is correct
3 Correct 3754 ms 35448 KB Output is correct
4 Correct 3101 ms 35292 KB Output is correct
5 Correct 4429 ms 35396 KB Output is correct
6 Correct 863 ms 34936 KB Output is correct
7 Correct 3713 ms 35272 KB Output is correct
8 Correct 3643 ms 35456 KB Output is correct
9 Correct 4453 ms 35480 KB Output is correct
10 Correct 841 ms 34936 KB Output is correct
11 Correct 3734 ms 35128 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24320 KB Output is correct
2 Correct 6482 ms 394480 KB Output is correct
3 Execution timed out 8073 ms 395372 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 24576 KB Output is correct
2 Correct 2755 ms 35228 KB Output is correct
3 Correct 3754 ms 35448 KB Output is correct
4 Correct 3101 ms 35292 KB Output is correct
5 Correct 4429 ms 35396 KB Output is correct
6 Correct 863 ms 34936 KB Output is correct
7 Correct 3713 ms 35272 KB Output is correct
8 Correct 3643 ms 35456 KB Output is correct
9 Correct 4453 ms 35480 KB Output is correct
10 Correct 841 ms 34936 KB Output is correct
11 Correct 3734 ms 35128 KB Output is correct
12 Correct 22 ms 24320 KB Output is correct
13 Correct 6482 ms 394480 KB Output is correct
14 Execution timed out 8073 ms 395372 KB Time limit exceeded
15 Halted 0 ms 0 KB -