oj.uz

Submission #1085022

# Submission time Handle Problem Language Result Execution time Memory
1085022 2024-09-07T10:11:21 Z pemguimn Factories (JOI14_factories) C++14
0 / 100
 1637 ms 144472 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];
}

map<pair<int, long long>, long long> mp;

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, 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);


    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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 26460 KB Output is correct
2 Correct 615 ms 44504 KB Output is correct
3 Correct 643 ms 44340 KB Output is correct
4 Incorrect 618 ms 44628 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26200 KB Output is correct
2 Correct 1171 ms 139796 KB Output is correct
3 Incorrect 1637 ms 144472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 26460 KB Output is correct
2 Correct 615 ms 44504 KB Output is correct
3 Correct 643 ms 44340 KB Output is correct
4 Incorrect 618 ms 44628 KB Output isn't correct
5 Halted 0 ms 0 KB -