oj.uz

Submission #43717

# Submission time Handle Problem Language Result Execution time Memory
43717 2018-03-21T08:09:23 Z aaron248 Factories (JOI14_factories) C++14
15 / 100
 6000 ms 291564 KB 
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,ll>
#define X first
#define Y second
const int maxn = 5e5 + 5;
const int mlog = 19;
const ll inf = 1e16;

int n;
vector<pii> way[maxn];
int h[maxn], par[maxn][21];
ll dist[maxn][21];
int sz[maxn], used[maxn];
int cpar[maxn];
ll far[maxn];

void dfs(int u, int last, ll lval) {
    h[u] = h[last] + 1;
    par[u][0] = last; dist[u][0] = lval;
    for(int i=1;i<=mlog;i++) {
        par[u][i] = par[par[u][i-1]][i-1];
        dist[u][i] = dist[u][i-1] + dist[par[u][i-1]][i-1];
    }
    for(auto t : way[u]) {
        int v = t.X; ll val = t.Y;
        if(v==last) continue;
        dfs(v, u, val);
    }
}

ll lca(int u, int v) {
    ll res = 0;
    if(h[u]<h[v]) swap(u, v);
    for(int i=mlog;i>=0;i--) {
        if(h[par[u][i]]>=h[v]) {
            res += dist[u][i];
            u = par[u][i];
        }
    }
    if(u==v) return res;
    for(int i=mlog;i>=0;i--) {
        if(par[u][i]!=par[v][i]) {
            res += dist[u][i] + dist[v][i];
            u = par[u][i]; v = par[v][i];
        }
    }
    return res + dist[u][0] + dist[v][0];
}

void survey(int u, int last) {
    sz[u] = 1;
    for(auto t : way[u]) {
        int v = t.X;
        if(v==last || used[v]) continue;
        survey(v, u);
        sz[u] += sz[v];
    }
}

int decom(int u) {
    survey(u,0);
    int x = u, last = 0;
    redo:
    for(auto t : way[x]) {
        int y = t.X;
        if(y==last || used[y]) continue;
        if(sz[y]>sz[u]/2) {
            last = x; x = y;
            goto redo;
        }
    }
    used[x] = 1;
    for(auto t : way[x]) {
        int y = t.X;
        if(used[y]) continue;
        int temp = decom(y);
        cpar[temp] = x;
    }
    return x;
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i=0;i<n-1;i++) {
        int x = A[i]+1, y = B[i]+1;
        ll val = D[i];
        way[x].push_back({y,val});
        way[y].push_back({x,val});
    }
    dfs(1,0,0);
    decom(1);
    for(int i=1;i<=n;i++) far[i] = inf;
}

ll Query(int S, int X[], int T, int Y[]) {
    for(int i=0;i<T;i++) {
        int u = Y[i]+1, x = u;
        while(x) {
            far[x] = min(far[x], lca(x, u));
            x = cpar[x];
        }
    }
    ll res = inf;
    for(int i=0;i<S;i++) {
        int u = X[i]+1, x = u;
        while(x) {
            res = min(res, far[x] + lca(x,u));
            x = cpar[x];
        }
    }
    for(int i=0;i<T;i++) {
        int u = Y[i]+1, x = u;
        while(x) {
            far[x] = inf;
            x = cpar[x];
        }
    }
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 12536 KB Output is correct
2 Correct 1359 ms 21856 KB Output is correct
3 Correct 2659 ms 31644 KB Output is correct
4 Correct 2601 ms 41228 KB Output is correct
5 Correct 3260 ms 51044 KB Output is correct
6 Correct 461 ms 60180 KB Output is correct
7 Correct 2517 ms 69852 KB Output is correct
8 Correct 2622 ms 79332 KB Output is correct
9 Correct 3302 ms 89088 KB Output is correct
10 Correct 512 ms 98164 KB Output is correct
11 Correct 2606 ms 107664 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 107664 KB Output is correct
2 Correct 4510 ms 271420 KB Output is correct
3 Execution timed out 6049 ms 291564 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6096 ms 291564 KB Time limit exceeded
2 Halted 0 ms 0 KB -