oj.uz

Submission #422661

# Submission time Handle Problem Language Result Execution time Memory
422661 2021-06-10T09:41:15 Z ACmachine Factories (JOI14_factories) C++17
100 / 100
 5722 ms 168548 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
 
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
const int INF = (int)1e9;
typedef long long ll;
const ll INFF = (ll)1e18;
int n;
vector<vector<array<ll, 2>>> vg;
vector<vector<array<ll, 2>>> g;
vector<ll> depth;
vector<int> lev;
vector<vector<int>> nxt;
vector<int> in;
vector<int> out;
vector<bool> type_a;
vector<bool> type_b;
vector<array<ll, 2>> dp;
int t = 0;
void dfs(int v, int p, ll d){
    in[v] = t++;
    depth[v] = d;
    if(p != -1){
        lev[v] = lev[p] + 1;
    }
    nxt[0][v] = p;
    FOR(i, 1, 20, 1){
        if(nxt[i - 1][v] != -1){
            nxt[i][v] = nxt[i - 1][nxt[i - 1][v]];
        }
    }
    for(auto x : g[v]){
        if(x[0] == p) continue;
        dfs(x[0], v, d + x[1]);
    }
    out[v] = t;
}
int lca(int u, int v){
    if(lev[u] < lev[v]) 
        swap(u, v);
    FORD(i, 19, 0, 1){
        if(lev[u] - (1 << i) >= lev[v]){
            u = nxt[i][u];
        }
    }
    if(u == v)
        return u;
    REPD(i, 19){
        if(nxt[i][u] != nxt[i][v]){
            u = nxt[i][u];
            v = nxt[i][v];
        }
    }
    return nxt[0][u];
}
int build_virtual_tree(vector<int> &vertices){
    auto upper = [&](int u, int v){
        return in[u] <= in[v] && out[u] >= out[v];
    };
    auto cmp = [&](int u, int v){
        return in[u] < in[v];
    };
    sort(vertices.begin(), vertices.end(), cmp);
    int up = vertices.size();
    REP(i, up - 1){
        vertices.pb(lca(vertices[i], vertices[i + 1]));
    }
    sort(vertices.begin(), vertices.end(), cmp);
    vertices.erase(unique(vertices.begin(), vertices.end()), vertices.end());
    for(int v : vertices){
        vg[v].clear();
        type_a[v] = false;
        type_b[v] = false;
    }
    vector<int> stk;
    stk.pb(vertices[0]);
    FOR(i, 1, vertices.size(), 1){
        while(stk.size() >= 2 && !upper(stk.back(), vertices[i])){
            int u = stk.back();
            stk.pop_back();
            int v = stk.back();
            ll w = abs(depth[u] - depth[v]);
            vg[u].pb({v, w});
            vg[v].pb({u, w});
        }
        stk.pb(vertices[i]);
    }
    while(stk.size() >= 2){
        int u = stk.back();
        stk.pop_back();
        int v = stk.back();
        ll w = abs(depth[u] - depth[v]);
        vg[u].pb({v, w});
        vg[v].pb({u, w});
    }
    return stk[0];
}
void solve(int v, int p, ll &ans){
    dp[v] = {INFF, INFF};
    for(auto x : vg[v]){
        if(x[0] == p) continue;
        solve(x[0], v, ans);
        auto ar = dp[x[0]];
        ar[0] += x[1]; 
        ar[1] += x[1];
        dp[v][0] = min(dp[v][0], ar[0]);
        dp[v][1] = min(dp[v][1], ar[1]);
    }
    if(type_a[v])
        dp[v][0] = 0;
    if(type_b[v])
        dp[v][1] = 0;
    ans = min(ans, dp[v][0] + dp[v][1]);
}
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    vg.resize(n);
    g.resize(n);
    depth.resize(n);
    nxt = vector<vector<int>>(20, vector<int>(n, -1));
    in.resize(n);
    out.resize(n);
    lev.resize(n, 0);
    type_a.resize(n, false);
    type_b.resize(n, false);
    dp.resize(n);
    REP(i, n - 1){
        g[A[i]].pb({B[i], D[i]});
        g[B[i]].pb({A[i], D[i]});
    }
    dfs(0, -1, 0); 
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<int> vertices;
    REP(i, S){
        vertices.pb(X[i]);
    }
    REP(i, T){
        vertices.pb(Y[i]);
    }
    int root = build_virtual_tree(vertices);
    REP(i, S){
        type_a[X[i]] = true;
    }
    REP(i, T){
        type_b[Y[i]] = true;
    }
    ll ans = INFF;
    solve(root, -1, ans);
    return ans;
}

Compilation message

factories.cpp: In function 'int build_virtual_tree(std::vector<int>&)':
factories.cpp:5:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
      |                                            ^
factories.cpp:82:5: note: in expansion of macro 'FOR'
   82 |     FOR(i, 1, vertices.size(), 1){
      |     ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 716 KB Output is correct
2 Correct 1014 ms 9808 KB Output is correct
3 Correct 1076 ms 9692 KB Output is correct
4 Correct 1026 ms 9800 KB Output is correct
5 Correct 892 ms 10092 KB Output is correct
6 Correct 693 ms 9668 KB Output is correct
7 Correct 1059 ms 9764 KB Output is correct
8 Correct 1024 ms 9864 KB Output is correct
9 Correct 867 ms 9924 KB Output is correct
10 Correct 696 ms 9612 KB Output is correct
11 Correct 1094 ms 9748 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 2679 ms 133320 KB Output is correct
3 Correct 3677 ms 136536 KB Output is correct
4 Correct 1848 ms 130704 KB Output is correct
5 Correct 3429 ms 165780 KB Output is correct
6 Correct 3952 ms 138344 KB Output is correct
7 Correct 3375 ms 36460 KB Output is correct
8 Correct 1877 ms 35704 KB Output is correct
9 Correct 2419 ms 41468 KB Output is correct
10 Correct 3374 ms 37664 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 716 KB Output is correct
2 Correct 1014 ms 9808 KB Output is correct
3 Correct 1076 ms 9692 KB Output is correct
4 Correct 1026 ms 9800 KB Output is correct
5 Correct 892 ms 10092 KB Output is correct
6 Correct 693 ms 9668 KB Output is correct
7 Correct 1059 ms 9764 KB Output is correct
8 Correct 1024 ms 9864 KB Output is correct
9 Correct 867 ms 9924 KB Output is correct
10 Correct 696 ms 9612 KB Output is correct
11 Correct 1094 ms 9748 KB Output is correct
12 Correct 3 ms 460 KB Output is correct
13 Correct 2679 ms 133320 KB Output is correct
14 Correct 3677 ms 136536 KB Output is correct
15 Correct 1848 ms 130704 KB Output is correct
16 Correct 3429 ms 165780 KB Output is correct
17 Correct 3952 ms 138344 KB Output is correct
18 Correct 3375 ms 36460 KB Output is correct
19 Correct 1877 ms 35704 KB Output is correct
20 Correct 2419 ms 41468 KB Output is correct
21 Correct 3374 ms 37664 KB Output is correct
22 Correct 4567 ms 143748 KB Output is correct
23 Correct 4310 ms 144184 KB Output is correct
24 Correct 4609 ms 147844 KB Output is correct
25 Correct 4876 ms 150560 KB Output is correct
26 Correct 5394 ms 142344 KB Output is correct
27 Correct 4283 ms 168548 KB Output is correct
28 Correct 3019 ms 138908 KB Output is correct
29 Correct 5722 ms 141116 KB Output is correct
30 Correct 5665 ms 140480 KB Output is correct
31 Correct 5666 ms 140992 KB Output is correct
32 Correct 1964 ms 45112 KB Output is correct
33 Correct 1715 ms 38488 KB Output is correct
34 Correct 2605 ms 35552 KB Output is correct
35 Correct 2632 ms 35260 KB Output is correct
36 Correct 2899 ms 36232 KB Output is correct
37 Correct 3065 ms 36188 KB Output is correct