oj.uz

Submission #1085023

# Submission time Handle Problem Language Result Execution time Memory
1085023 2024-09-07T10:14:10 Z pemguimn Factories (JOI14_factories) C++14
100 / 100
 2561 ms 191440 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 26456 KB Output is correct
2 Correct 631 ms 42576 KB Output is correct
3 Correct 646 ms 42320 KB Output is correct
4 Correct 625 ms 42580 KB Output is correct
5 Correct 565 ms 44860 KB Output is correct
6 Correct 409 ms 44464 KB Output is correct
7 Correct 645 ms 44384 KB Output is correct
8 Correct 629 ms 44628 KB Output is correct
9 Correct 531 ms 44772 KB Output is correct
10 Correct 427 ms 44368 KB Output is correct
11 Correct 705 ms 44376 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26204 KB Output is correct
2 Correct 1205 ms 135508 KB Output is correct
3 Correct 1614 ms 140180 KB Output is correct
4 Correct 857 ms 136856 KB Output is correct
5 Correct 1460 ms 185172 KB Output is correct
6 Correct 1750 ms 146344 KB Output is correct
7 Correct 1076 ms 68176 KB Output is correct
8 Correct 523 ms 67304 KB Output is correct
9 Correct 788 ms 75344 KB Output is correct
10 Correct 1038 ms 69460 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 26456 KB Output is correct
2 Correct 631 ms 42576 KB Output is correct
3 Correct 646 ms 42320 KB Output is correct
4 Correct 625 ms 42580 KB Output is correct
5 Correct 565 ms 44860 KB Output is correct
6 Correct 409 ms 44464 KB Output is correct
7 Correct 645 ms 44384 KB Output is correct
8 Correct 629 ms 44628 KB Output is correct
9 Correct 531 ms 44772 KB Output is correct
10 Correct 427 ms 44368 KB Output is correct
11 Correct 705 ms 44376 KB Output is correct
12 Correct 13 ms 26204 KB Output is correct
13 Correct 1205 ms 135508 KB Output is correct
14 Correct 1614 ms 140180 KB Output is correct
15 Correct 857 ms 136856 KB Output is correct
16 Correct 1460 ms 185172 KB Output is correct
17 Correct 1750 ms 146344 KB Output is correct
18 Correct 1076 ms 68176 KB Output is correct
19 Correct 523 ms 67304 KB Output is correct
20 Correct 788 ms 75344 KB Output is correct
21 Correct 1038 ms 69460 KB Output is correct
22 Correct 2270 ms 156084 KB Output is correct
23 Correct 1993 ms 157328 KB Output is correct
24 Correct 2383 ms 161640 KB Output is correct
25 Correct 2435 ms 165152 KB Output is correct
26 Correct 2432 ms 154448 KB Output is correct
27 Correct 2141 ms 191440 KB Output is correct
28 Correct 1385 ms 152236 KB Output is correct
29 Correct 2554 ms 153172 KB Output is correct
30 Correct 2561 ms 152480 KB Output is correct
31 Correct 2561 ms 152768 KB Output is correct
32 Correct 930 ms 77432 KB Output is correct
33 Correct 612 ms 71104 KB Output is correct
34 Correct 962 ms 66896 KB Output is correct
35 Correct 929 ms 66640 KB Output is correct
36 Correct 1075 ms 67664 KB Output is correct
37 Correct 1087 ms 67656 KB Output is correct