oj.uz

Submission #877721

# Submission time Handle Problem Language Result Execution time Memory
877721 2023-11-23T13:16:52 Z hafo Factories (JOI14_factories) C++14
100 / 100
 2866 ms 155948 KB 
#include"factories.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 19;
const int maxn = 5e5 + 7;
const ll oo = 1e18 + 69;

int n, q, mark[maxn], A[maxn], B[maxn], D[maxn], X[maxn], Y[maxn], S, T, st[maxn], en[maxn], timer = 0, cur;
vector<pa> g[maxn];
ll dp[maxn][2], f[maxn], ans;
vector<int> node;

bool cmp(int i, int j) {
    return st[i] < st[j];
}

struct LCA {
    int p[LOG][maxn], dep[maxn];

    void dfs(int u, int par) {
        for(auto e:g[u]) {
            int v = e.fi, w = e.se;
            if(v == par) continue;
            dep[v] = dep[u] + 1;
            p[0][v] = u;
            dfs(v, u);
        }
    }

    void init() {
        memset(p, -1, sizeof p);
        dep[0] = 0;
        dfs(0, 0);
        for(int i = 1; i < LOG; i++) {
            for(int u = 0; u < n; u++) p[i][u] = p[i - 1][p[i - 1][u]];
        }
    }

    int get_lca(int u, int v) {
        if(dep[u] < dep[v]) swap(u, v);
        int k = dep[u] - dep[v];
        for(int i = 0; i < LOG; i++) 
            if((k >> i) & 1) u = p[i][u];

        if(u == v) return u;

        for(int i = LOG - 1; i >= 0; i--) 
            if(p[i][u] != p[i][v]) {
                u = p[i][u];
                v = p[i][v];
            }
        return p[0][u];
    }

} lca;

void dfs(int u, int par) {
    st[u] = ++timer;
    for(auto e:g[u]) {
        int v = e.fi, w = e.se;
        if(v == par) continue;
        f[v] = f[u] + w;
        dfs(v, u);
    }
    en[u] = timer;
}

void dfs2(int u) {
    if(mark[u] == 1) dp[u][0] = 0;
    if(mark[u] == 2) dp[u][1] = 0;
    if(mark[u] == 3) {
        dp[u][0] = 0;
        dp[u][1] = 0;
    }
    mark[u] = 0;
    cur++;
    while(cur < Size(node)) {
        int v = node[cur];
        if(st[u] <= st[v] && st[v] <= en[u]) {
            dfs2(v);
            mini(ans, dp[u][0] + dp[v][1] + f[v] - f[u]);
            mini(ans, dp[u][1] + dp[v][0] + f[v] - f[u]);
            mini(dp[u][0], dp[v][0] + f[v] - f[u]);
            mini(dp[u][1], dp[v][1] + f[v] - f[u]);
        } else break;
    }
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    for(int i = 0; i < n - 1; i++) {
        g[A[i]].pb({B[i], D[i]});
        g[B[i]].pb({A[i], D[i]});
    }       

    for(int i = 0; i < n; i++) 
        for(int j = 0; j < 2; j++) dp[i][j] = oo;
    dfs(0, 0);
    lca.init(); 
}

long long Query(int S, int X[], int T, int Y[]){
    for(int i = 0; i < S; i++) {
        node.pb(X[i]);
        mark[X[i]] = 1;
    }
    for(int i = 0; i < T; i++) {
        node.pb(Y[i]);
        if(mark[Y[i]] == 1) mark[Y[i]] = 3;
        else if(mark[Y[i]] == 0) mark[Y[i]] = 2;
    }

    sort(all(node), cmp);
    for(int i = 1; i < S + T; i++) {
        int par = lca.get_lca(node[i], node[i - 1]);
        if(!mark[par]) {
            mark[par] = 4;
            node.pb(par);
        }
    }

    if(!mark[0]) {
        mark[0] = 4;
        node.pb(0);
    }

    sort(all(node), cmp);
    cur = 0;
    ans = oo;
    dfs2(0);

    for(auto i:node) {
        mark[i] = 0;
        dp[i][0] = dp[i][1] = oo;
    }
    node.clear();
    return ans;
}

Compilation message

factories.cpp: In member function 'void LCA::dfs(int, int)':
factories.cpp:37:27: warning: unused variable 'w' [-Wunused-variable]
   37 |             int v = e.fi, w = e.se;
      |                           ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 76636 KB Output is correct
2 Correct 596 ms 92376 KB Output is correct
3 Correct 637 ms 92372 KB Output is correct
4 Correct 578 ms 92496 KB Output is correct
5 Correct 485 ms 92496 KB Output is correct
6 Correct 528 ms 92380 KB Output is correct
7 Correct 596 ms 92496 KB Output is correct
8 Correct 589 ms 92420 KB Output is correct
9 Correct 502 ms 92500 KB Output is correct
10 Correct 524 ms 92500 KB Output is correct
11 Correct 606 ms 92500 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 76380 KB Output is correct
2 Correct 1170 ms 130972 KB Output is correct
3 Correct 1580 ms 133076 KB Output is correct
4 Correct 842 ms 131448 KB Output is correct
5 Correct 1337 ms 155308 KB Output is correct
6 Correct 1797 ms 133952 KB Output is correct
7 Correct 830 ms 103748 KB Output is correct
8 Correct 494 ms 103616 KB Output is correct
9 Correct 602 ms 106540 KB Output is correct
10 Correct 834 ms 104276 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 76636 KB Output is correct
2 Correct 596 ms 92376 KB Output is correct
3 Correct 637 ms 92372 KB Output is correct
4 Correct 578 ms 92496 KB Output is correct
5 Correct 485 ms 92496 KB Output is correct
6 Correct 528 ms 92380 KB Output is correct
7 Correct 596 ms 92496 KB Output is correct
8 Correct 589 ms 92420 KB Output is correct
9 Correct 502 ms 92500 KB Output is correct
10 Correct 524 ms 92500 KB Output is correct
11 Correct 606 ms 92500 KB Output is correct
12 Correct 13 ms 76380 KB Output is correct
13 Correct 1170 ms 130972 KB Output is correct
14 Correct 1580 ms 133076 KB Output is correct
15 Correct 842 ms 131448 KB Output is correct
16 Correct 1337 ms 155308 KB Output is correct
17 Correct 1797 ms 133952 KB Output is correct
18 Correct 830 ms 103748 KB Output is correct
19 Correct 494 ms 103616 KB Output is correct
20 Correct 602 ms 106540 KB Output is correct
21 Correct 834 ms 104276 KB Output is correct
22 Correct 2080 ms 136432 KB Output is correct
23 Correct 2037 ms 137804 KB Output is correct
24 Correct 2086 ms 138740 KB Output is correct
25 Correct 2128 ms 140820 KB Output is correct
26 Correct 2337 ms 138616 KB Output is correct
27 Correct 1801 ms 155948 KB Output is correct
28 Correct 1600 ms 138792 KB Output is correct
29 Correct 2564 ms 138104 KB Output is correct
30 Correct 2833 ms 137520 KB Output is correct
31 Correct 2866 ms 138084 KB Output is correct
32 Correct 852 ms 107848 KB Output is correct
33 Correct 902 ms 104500 KB Output is correct
34 Correct 1100 ms 102412 KB Output is correct
35 Correct 999 ms 102324 KB Output is correct
36 Correct 963 ms 102888 KB Output is correct
37 Correct 1016 ms 102868 KB Output is correct