Submission #1085023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085023		pemguimn	Factories (JOI14_factories)	C++14	100 / 100	2561 ms	191440 KiB

factories

#include <bits/stdc++.h>
//#include "factories.h"

using namespace std;

const int maxN = 5e5 + 5, LOG = 20;
const long long INF = (long long) 1e18 + 5;
vector<pair<int, long long>> adj[maxN];

int h[maxN], par[LOG][maxN], tin[maxN], tout[maxN], timedfs = 0;

long long w[maxN];
void dfs(int i, int pre){
    tin[i] = ++timedfs;
    for(pair<int, long long> e : adj[i]){
        int x = e.first, c = e.second;
        if(x == pre) continue;
        h[x] = h[i] + 1, w[x] = w[i] + c;
        par[0][x] = i;
        for(int j = 1; j < LOG; j++) par[j][x] = par[j - 1][par[j - 1][x]];
        dfs(x, i);
    }
    tout[i] = timedfs;
}

int lca(int x, int y){
    if(h[x] < h[y]) swap(x, y);
    int d = h[x] - h[y];
    for(int i = 0; i < LOG; i++){
        if(d & (1 << i)) x = par[i][x];
    }
    if(x == y) return x;
    for(int i = LOG - 1; i >= 0; i--){
        if(par[i][x] != par[i][y]) x = par[i][x], y = par[i][y];
    }
    return par[0][x];
}

int label[maxN];

void Init(int N, int A[], int B[], int D[]){
    for(int i = 0; i < N - 1; i++){
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    dfs(0, 0);
    memset(label, -1, sizeof label);
}

vector<pair<int, long long>> adj2[maxN];

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

long long dp[2][maxN], ans;
void dfs2(int i){
    for(pair<int, long long> e : adj2[i]){
        int x = e.first;
        long long w = e.second;
        dfs2(x);
        dp[0][i] = min(dp[0][i], dp[0][x] + w);
        dp[1][i] = min(dp[1][i], dp[1][x] + w);
    }
    if(label[i] != -1){
        dp[label[i]][i] = 0;
    }
    ans = min(ans, dp[0][i] + dp[1][i]);
}
long long Query(int S, int X[], int T, int Y[]){
    vector<int> v; ans = INF;
    for(int i = 0; i < S; i++){
        if(label[X[i]] == 1) return 0;
        v.push_back(X[i]), label[X[i]] = 0;
    }
    for(int i = 0; i < T; i++){
        if(label[Y[i]] == 0) return 0;
        v.push_back(Y[i]), label[Y[i]] = 1;
    }
    sort(v.begin(), v.end(), [](int x, int y){return tin[x] < tin[y];});
    for(int i = v.size() - 2; i >= 0; i--){
        v.push_back(lca(v[i], v[i + 1]));
    }
    sort(v.begin(), v.end(), [](int x, int y){return tin[x] < tin[y];});
    v.resize(unique(v.begin(), v.end()) - v.begin());
    stack<int> st; st.push(v[0]);
    for(int i = 1; i < (int) v.size(); i++){
        while(st.size() && !in(st.top(), v[i])) st.pop();
        adj2[st.top()].push_back({v[i], w[v[i]] - w[st.top()]});
        st.push(v[i]);
    }
    for(int x : v) dp[0][x] = dp[1][x] = INF;
    dfs2(v[0]);
    for(int x : v) label[x] = -1;
    for(int x : v) adj2[x].clear();
    while(st.size()) st.pop();

    return ans;
}

#ifdef LOCAL
const int MAX = 1e3 + 5;
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//
    freopen("factories.inp", "r", stdin);
//    freopen("factories.out", "w", stdout);

    int n, q; cin >> n >> q;
    int x[MAX], y[MAX], d[MAX];
    for(int i = 0; i < n - 1; i++){
        cin >> x[i] >> y[i] >> d[i];
    }
    Init(n, x, y, d);
    for(int i = 1; i <= q; i++){
        int s, t; cin >> s >> t;
        int a[MAX], b[MAX];
        for(int i = 0; i < s; i++) cin >> a[i];
        for(int i = 0; i < t; i++) cin >> b[i];
        cout << Query(s, a, t, b) << '\n';
    }
    return 0;
}
#endif

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67