Submission #422661

#	Time	Username	Problem	Language	Result	Execution time	Memory
422661		ACmachine	Factories (JOI14_factories)	C++17	100 / 100	5722 ms	168548 KiB

factories

#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 (stderr)

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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67