oj.uz

Submission #47709

# Submission time Handle Problem Language Result Execution time Memory
47709 2018-05-06T11:37:18 Z qoo2p5 Factories (JOI14_factories) C++17
100 / 100
 4703 ms 524288 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

bool mini(auto &x, const auto &y) {
    if (y < x) {
        x = y;
        return 1;
    }
    return 0;
}

bool maxi(auto &x, const auto &y) {
    if (y > x) {
        x = y;
        return 1;
    }
    return 0;
}

const int N = (int) 5e5 + 123;
const int L = 20;

int n;
vector<pair<int, int>> g[N];
ll len[N];
int depth[N];
int up[N][L];
int tin[N], tout[N];

void precalc(int v, int f = 0) {
    static int tmr = 0;
    tin[v] = tmr++;
    up[v][0] = f;
    rep(i, 1, L) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for (auto &e : g[v]) {
        int u = e.first;
        if (u == f) {
            continue;
        }
        len[u] = len[v] + e.second;
        depth[u] = depth[v] + 1;
        precalc(u, v);
    }
    tout[v] = tmr - 1;
}

bool test(int mask, int bit) {
    return mask & (1 << bit);
}

int go(int v, int h) {
    rep(i, 0, L) {
        if (test(h, i)) {
            v = up[v][i];
        }
    }
    return v;
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    u = go(u, depth[u] - depth[v]);
    if (u == v) {
        return u;
    }
    per(i, L - 1, 0) {
        int uu = up[u][i], vv = up[v][i];
        if (uu != vv) {
            u = uu, v = vv;
        }
    }
    return up[u][0];
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    rep(i, 0, n - 1) {
        g[A[i]].pb({B[i], D[i]});
        g[B[i]].pb({A[i], D[i]});
    }
    precalc(0);
}

vector<int> adj[N];

bool in(int v, int u) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

ll dp1[N], dp2[N];

ll dfs(int v) {
    ll res = LINF;
    for (int u : adj[v]) {
        mini(res, dfs(u));
        mini(dp1[v], dp1[u] + len[u] - len[v]);
        mini(dp2[v], dp2[u] + len[u] - len[v]);
    }
    mini(res, dp1[v] + dp2[v]);
    return res;
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<int> p;
    rep(i, 0, S) {
        p.pb(X[i]);
    }
    rep(i, 0, T) {
        p.pb(Y[i]);
    }
    sort(all(p), [] (int i, int j) {
        return tin[i] < tin[j];
    });
    vector<int> q;
    rep(i, 0, sz(p) - 1) {
        q.pb(lca(p[i], p[i + 1]));
    }
    for (int v : q) {
        p.pb(v);
    }
    sort(all(p));
    p.resize(unique(all(p)) - p.begin());
    sort(all(p), [] (int i, int j) {
        return tin[i] < tin[j];
    });
    
    for (int v : p) {
        dp1[v] = LINF;
        dp2[v] = LINF;
        adj[v].clear();
    }
    
    vector<int> st;
    st.pb(p[0]);
    rep(i, 1, sz(p)) {
        int v = p[i];
        while (!in(v, st.back())) {
            st.pop_back();
        }
        adj[st.back()].pb(v);
        st.pb(v);
    }
    rep(i, 0, S) {
        dp1[X[i]] = 0;
    }
    rep(i, 0, T) {
        dp2[Y[i]] = 0;
    }
    return dfs(p[0]);
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 24440 KB Output is correct
2 Correct 1238 ms 42772 KB Output is correct
3 Correct 1306 ms 52440 KB Output is correct
4 Correct 1284 ms 61932 KB Output is correct
5 Correct 1056 ms 71436 KB Output is correct
6 Correct 919 ms 80612 KB Output is correct
7 Correct 1299 ms 90164 KB Output is correct
8 Correct 1266 ms 99748 KB Output is correct
9 Correct 1101 ms 109452 KB Output is correct
10 Correct 923 ms 118700 KB Output is correct
11 Correct 1320 ms 128328 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 128328 KB Output is correct
2 Correct 2092 ms 226212 KB Output is correct
3 Correct 2826 ms 246444 KB Output is correct
4 Correct 1534 ms 263108 KB Output is correct
5 Correct 2909 ms 312020 KB Output is correct
6 Correct 3332 ms 312020 KB Output is correct
7 Correct 2662 ms 312020 KB Output is correct
8 Correct 1417 ms 312020 KB Output is correct
9 Correct 2530 ms 312020 KB Output is correct
10 Correct 2542 ms 312020 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 3803 ms 388248 KB Output is correct
2 Correct 3670 ms 414176 KB Output is correct
3 Correct 4354 ms 441352 KB Output is correct
4 Correct 4442 ms 467880 KB Output is correct
5 Correct 4567 ms 484076 KB Output is correct
6 Correct 3972 ms 524288 KB Output is correct
7 Correct 2477 ms 524288 KB Output is correct
8 Correct 4690 ms 524288 KB Output is correct
9 Correct 4682 ms 524288 KB Output is correct
10 Correct 4703 ms 524288 KB Output is correct
11 Correct 2194 ms 524288 KB Output is correct
12 Correct 1559 ms 524288 KB Output is correct
13 Correct 2258 ms 524288 KB Output is correct
14 Correct 2252 ms 524288 KB Output is correct
15 Correct 2548 ms 524288 KB Output is correct
16 Correct 2486 ms 524288 KB Output is correct