oj.uz

Submission #246908

# Submission time Handle Problem Language Result Execution time Memory
246908 2020-07-10T13:56:31 Z receed Factories (JOI14_factories) C++14
100 / 100
 5297 ms 139644 KB 
#include "factories.h"
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 500001, L = 19;
vector<pair<ll, ll>> g[N];
int tin[N], tout[N], ct, up[L][N], th[N], par[N], st[N], li[N * 2];
ll h[N], d1[N], d2[N], inf = 1e16;

void dfs(int v, int p) {
    up[0][v] = p;
    tin[v] = ++ct;
    for (auto &u : g[v])
        if (u.first != p) {
            h[u.first] = h[v] + u.second;
            th[u.first] = th[v] + 1;
            dfs(u.first, v);
        }
    tout[v] = ++ct;
}

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

int lca(int u, int v) {
    if (isp(u, v))
        return u;
    for (int i = L - 1; i >= 0; i--)
        if (!isp(up[i][u], v))
            u = up[i][u];
    return up[0][u];
}

void Init(int n, int a[], int b[], int d[]) {
    rep(i, n - 1) {
        g[a[i]].push_back({b[i], d[i]});
        g[b[i]].push_back({a[i], d[i]});
    }
    dfs(0, 0);
    rep(i, L - 1)
        rep(j, n)
            up[i + 1][j] = up[i][up[i][j]];
    rep(i, n)
        d1[i] = d2[i] = inf;
}

long long Query(int s, int x[], int t, int y[]) {
    int lp = 0;
    rep(i, s) {
        li[lp++] = x[i];
        d1[x[i]] = 0;
    }
    rep(i, t) {
        li[lp++] = y[i];
        d2[y[i]] = 0;
    }
    sort(li, li + lp, [](int v1, int v2) {return tin[v1] < tin[v2];});
    int k = lp;
    rep(i, k - 1)
        li[lp++] = lca(li[i], li[i + 1]);
    sort(li, li + lp, [](int v1, int v2) {return tin[v1] < tin[v2];});
    lp = unique(li, li + lp) - li;
    int sp = 0;
    rep(j, lp) {
        int i = li[j];
        if (sp == 0)
            st[sp++] = i;
        else {
            while (tout[st[sp - 1]] < tout[i])
                sp--;
            par[i] = st[sp - 1];
            st[sp++] = i;
        }
    }
    ll ans = inf;
    for (int i = lp - 1; i > 0; i--) {
        ll v = li[i], cd = h[v] - h[par[v]];
        d1[v] += cd;
        d2[v] += cd;
        ans = min(ans, min(d1[v] + d2[par[v]], d2[v] + d1[par[v]]));
        d1[par[v]] = min(d1[par[v]], d1[v]);
        d2[par[v]] = min(d2[par[v]], d2[v]);
    }
    rep(i, lp)
        d1[li[i]] = d2[li[i]] = inf;
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12800 KB Output is correct
2 Correct 997 ms 29620 KB Output is correct
3 Correct 986 ms 29560 KB Output is correct
4 Correct 928 ms 29688 KB Output is correct
5 Correct 712 ms 29304 KB Output is correct
6 Correct 826 ms 29048 KB Output is correct
7 Correct 896 ms 28968 KB Output is correct
8 Correct 912 ms 29048 KB Output is correct
9 Correct 719 ms 29308 KB Output is correct
10 Correct 836 ms 29264 KB Output is correct
11 Correct 915 ms 29152 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12544 KB Output is correct
2 Correct 2588 ms 118536 KB Output is correct
3 Correct 2715 ms 118520 KB Output is correct
4 Correct 2291 ms 114548 KB Output is correct
5 Correct 1318 ms 139644 KB Output is correct
6 Correct 3029 ms 122588 KB Output is correct
7 Correct 2893 ms 47040 KB Output is correct
8 Correct 2734 ms 46784 KB Output is correct
9 Correct 1033 ms 50168 KB Output is correct
10 Correct 2786 ms 48388 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12800 KB Output is correct
2 Correct 997 ms 29620 KB Output is correct
3 Correct 986 ms 29560 KB Output is correct
4 Correct 928 ms 29688 KB Output is correct
5 Correct 712 ms 29304 KB Output is correct
6 Correct 826 ms 29048 KB Output is correct
7 Correct 896 ms 28968 KB Output is correct
8 Correct 912 ms 29048 KB Output is correct
9 Correct 719 ms 29308 KB Output is correct
10 Correct 836 ms 29264 KB Output is correct
11 Correct 915 ms 29152 KB Output is correct
12 Correct 14 ms 12544 KB Output is correct
13 Correct 2588 ms 118536 KB Output is correct
14 Correct 2715 ms 118520 KB Output is correct
15 Correct 2291 ms 114548 KB Output is correct
16 Correct 1318 ms 139644 KB Output is correct
17 Correct 3029 ms 122588 KB Output is correct
18 Correct 2893 ms 47040 KB Output is correct
19 Correct 2734 ms 46784 KB Output is correct
20 Correct 1033 ms 50168 KB Output is correct
21 Correct 2786 ms 48388 KB Output is correct
22 Correct 4536 ms 115756 KB Output is correct
23 Correct 4391 ms 118224 KB Output is correct
24 Correct 4205 ms 118600 KB Output is correct
25 Correct 4294 ms 122240 KB Output is correct
26 Correct 4772 ms 117908 KB Output is correct
27 Correct 2061 ms 132640 KB Output is correct
28 Correct 4065 ms 113660 KB Output is correct
29 Correct 5297 ms 115536 KB Output is correct
30 Correct 5249 ms 117376 KB Output is correct
31 Correct 4813 ms 117656 KB Output is correct
32 Correct 1183 ms 58744 KB Output is correct
33 Correct 2256 ms 55132 KB Output is correct
34 Correct 2987 ms 51576 KB Output is correct
35 Correct 2691 ms 51576 KB Output is correct
36 Correct 2657 ms 52288 KB Output is correct
37 Correct 2531 ms 52228 KB Output is correct