oj.uz

Submission #305906

# Submission time Handle Problem Language Result Execution time Memory
305906 2020-09-24T05:01:12 Z limabeans Factories (JOI14_factories) C++17
15 / 100
 8000 ms 395428 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 62 ms 24576 KB Output is correct
2 Correct 2796 ms 35140 KB Output is correct
3 Correct 3722 ms 34940 KB Output is correct
4 Correct 3120 ms 35520 KB Output is correct
5 Correct 4431 ms 35628 KB Output is correct
6 Correct 862 ms 35064 KB Output is correct
7 Correct 3724 ms 35072 KB Output is correct
8 Correct 3529 ms 34936 KB Output is correct
9 Correct 4381 ms 35416 KB Output is correct
10 Correct 838 ms 35064 KB Output is correct
11 Correct 3682 ms 35268 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24320 KB Output is correct
2 Correct 6682 ms 394376 KB Output is correct
3 Execution timed out 8080 ms 395428 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 24576 KB Output is correct
2 Correct 2796 ms 35140 KB Output is correct
3 Correct 3722 ms 34940 KB Output is correct
4 Correct 3120 ms 35520 KB Output is correct
5 Correct 4431 ms 35628 KB Output is correct
6 Correct 862 ms 35064 KB Output is correct
7 Correct 3724 ms 35072 KB Output is correct
8 Correct 3529 ms 34936 KB Output is correct
9 Correct 4381 ms 35416 KB Output is correct
10 Correct 838 ms 35064 KB Output is correct
11 Correct 3682 ms 35268 KB Output is correct
12 Correct 21 ms 24320 KB Output is correct
13 Correct 6682 ms 394376 KB Output is correct
14 Execution timed out 8080 ms 395428 KB Time limit exceeded
15 Halted 0 ms 0 KB -