oj.uz

Submission #495587

# Submission time Handle Problem Language Result Execution time Memory
495587 2021-12-19T11:44:50 Z K4YAN Factories (JOI14_factories) C++17
100 / 100
 5109 ms 246640 KB 
//Be Name Khoda

#include<bits/stdc++.h>
#include "factories.h"
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
#define ll long long
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pll pair<ll, ll>

const ll mxn = 5e5 + 16, INF = 1e15 + 32;
ll n, m, q, w, ans;
ll st[mxn], fn[mxn], h[mxn], dis[mxn], c[mxn], dp[mxn][3], par[mxn][20];
vector<ll> f, g;
vector<pll> adj[mxn], G[mxn];
set<ll> s;
bitset<mxn> mark;

void DFS(int v) {

    mark.set(v);
    st[v] = q++, fn[v] = q, h[v] = w++;
    for(int i = 1; i < 20; i++) {
        par[v][i] = par[par[v][i - 1]][i - 1];
    }
    for(auto u : adj[v]) {
        if(!mark[u.first]) {
            par[u.first][0] = v;
            dis[u.first] = dis[v] + u.second;
            DFS(u.first);
            fn[v] = fn[u.first];
        }
    } w--;

}

void Init(int N, int A[], int B[], int D[]) {

    n = N;
    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]});
    }
    q = w = 0;
    DFS(1);
    mark.reset();

}

inline void clr() {
    for(auto u : f) {
        c[u] = 0;
    } f.clear(); 
    return;
}

bool comp(int a, int b) {
    return st[a] < st[b];
}

ll find_lca(ll v, ll u) {
    if(v == u) return v;
    if(h[v] > h[u]) {
        swap(v, u);
    }
    for(int i = 19; i > -1; i--) {
        if(h[u] - (1LL << i) < h[v]) continue;
        u = par[u][i];
    }
    if(v == u) return v;
    for(int i = 19; i > -1; i--) {
        if(par[u][i] != par[v][i]) {
            u = par[u][i], v = par[v][i];
        }
    } return par[v][0];
}

inline void build_Graph() {
    stack<ll> sk;
    sk.push(g[0]); dp[g[0]][0] = dp[g[0]][1] = dp[g[0]][2] = INF;
    for(int i = 1; i < int(g.size()); i++) {
        while(fn[sk.top()] < fn[g[i]]) sk.pop();
        dp[g[i]][0] = dp[g[i]][1] = dp[g[i]][2] = INF;
        G[sk.top()].push_back({g[i], dis[g[i]] - dis[sk.top()]});
        sk.push(g[i]);
    }
}

void solve_dp(int v) {

    if(c[v] > 0) {
        dp[v][c[v] % 2] = 0;
    }
    for(auto u : G[v]) {
        solve_dp(u.first);
        dp[v][2] = min(dp[v][2], dp[u.first][2]);
        dp[v][1] = min(dp[v][1], dp[u.first][1] + u.second);
        dp[v][0] = min(dp[v][0], dp[u.first][0] + u.second);
    }
    dp[v][2] = min(dp[v][2], dp[v][1] + dp[v][0]);
    return;

}

ll Query(int S, int X[], int T, int Y[]) {

    for(auto u : g) {
        G[u].clear();
    } clr(); s.clear(), f.clear(), g.clear();

    for(int i = 0; i < S; i++) {
        c[++X[i]] = 1; f.push_back(X[i]); s.insert(X[i]);
    } for(int i = 0; i < T; i++) {
        c[++Y[i]] += 2;
        f.push_back(Y[i]); s.insert(Y[i]);
        if(c[Y[i]] == 3) {
            return 0;
        }
    }
    sort(all(f), comp);
    g = f;
    for(int i = 0; i < int(f.size()) - 1; i++) {
        w = find_lca(f[i], f[i + 1]);
        if(!s.count(w)) {
            s.insert(w);
            g.push_back(w);
        }
    }
    sort(all(g), comp);
    build_Graph();
    solve_dp(g[0]);
    ans = dp[g[0]][2];
    return ans;

}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 24268 KB Output is correct
2 Correct 1287 ms 43208 KB Output is correct
3 Correct 1361 ms 43040 KB Output is correct
4 Correct 1322 ms 43280 KB Output is correct
5 Correct 1125 ms 43392 KB Output is correct
6 Correct 941 ms 42976 KB Output is correct
7 Correct 1335 ms 42928 KB Output is correct
8 Correct 1313 ms 43320 KB Output is correct
9 Correct 1099 ms 43460 KB Output is correct
10 Correct 931 ms 42980 KB Output is correct
11 Correct 1297 ms 43088 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24140 KB Output is correct
2 Correct 1662 ms 190896 KB Output is correct
3 Correct 2441 ms 195328 KB Output is correct
4 Correct 1062 ms 187876 KB Output is correct
5 Correct 2102 ms 236120 KB Output is correct
6 Correct 2600 ms 197416 KB Output is correct
7 Correct 2490 ms 76704 KB Output is correct
8 Correct 1096 ms 76012 KB Output is correct
9 Correct 1956 ms 83808 KB Output is correct
10 Correct 2446 ms 78076 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 24268 KB Output is correct
2 Correct 1287 ms 43208 KB Output is correct
3 Correct 1361 ms 43040 KB Output is correct
4 Correct 1322 ms 43280 KB Output is correct
5 Correct 1125 ms 43392 KB Output is correct
6 Correct 941 ms 42976 KB Output is correct
7 Correct 1335 ms 42928 KB Output is correct
8 Correct 1313 ms 43320 KB Output is correct
9 Correct 1099 ms 43460 KB Output is correct
10 Correct 931 ms 42980 KB Output is correct
11 Correct 1297 ms 43088 KB Output is correct
12 Correct 16 ms 24140 KB Output is correct
13 Correct 1662 ms 190896 KB Output is correct
14 Correct 2441 ms 195328 KB Output is correct
15 Correct 1062 ms 187876 KB Output is correct
16 Correct 2102 ms 236120 KB Output is correct
17 Correct 2600 ms 197416 KB Output is correct
18 Correct 2490 ms 76704 KB Output is correct
19 Correct 1096 ms 76012 KB Output is correct
20 Correct 1956 ms 83808 KB Output is correct
21 Correct 2446 ms 78076 KB Output is correct
22 Correct 4177 ms 212120 KB Output is correct
23 Correct 3691 ms 213768 KB Output is correct
24 Correct 5109 ms 219100 KB Output is correct
25 Correct 4788 ms 222668 KB Output is correct
26 Correct 4484 ms 204884 KB Output is correct
27 Correct 4194 ms 246640 KB Output is correct
28 Correct 2513 ms 205072 KB Output is correct
29 Correct 4339 ms 204012 KB Output is correct
30 Correct 4370 ms 203216 KB Output is correct
31 Correct 4367 ms 204060 KB Output is correct
32 Correct 2365 ms 90592 KB Output is correct
33 Correct 1659 ms 84728 KB Output is correct
34 Correct 2323 ms 75488 KB Output is correct
35 Correct 2250 ms 75364 KB Output is correct
36 Correct 2827 ms 76304 KB Output is correct
37 Correct 2728 ms 76156 KB Output is correct