oj.uz

Submission #305886

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


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

long long Query(int S, int X[], int T, int Y[]) {
    ll res = inf;
    for (int i=0; i<S; i++) {
	for (int j=0; j<T; j++) {
	    int u = X[i];
	    int v = Y[j];
	    res = min(res, dist(u, v));
	}
    }
    return res;
}




int N, Q;
int A[maxn], B[maxn], D[maxn];
int S, T, X[maxn], Y[maxn];

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 12800 KB Output is correct
2 Execution timed out 8045 ms 30472 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12416 KB Output is correct
2 Correct 2924 ms 96452 KB Output is correct
3 Correct 5855 ms 115588 KB Output is correct
4 Correct 1750 ms 111552 KB Output is correct
5 Correct 4694 ms 135144 KB Output is correct
6 Correct 4462 ms 117816 KB Output is correct
7 Execution timed out 8087 ms 50704 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 12800 KB Output is correct
2 Execution timed out 8045 ms 30472 KB Time limit exceeded
3 Halted 0 ms 0 KB -