oj.uz

Submission #993767

# Submission time Handle Problem Language Result Execution time Memory
993767 2024-06-06T12:02:12 Z Valaki2 Factories (JOI14_factories) C++14
33 / 100
 8000 ms 182596 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 5e5;
const ll inf = 1e16 + 42;

struct edge {
    int to;
    ll wei;
    int subtree_size;
    edge() : to(0), wei(0ll), subtree_size(0) {}
    edge(int to_, ll wei_, int subtree_size_) :
        to(to_), wei(wei_), subtree_size(subtree_size_) {}
};

const int logn = 20;

int n;
vector<edge > graph[1 + maxn];
bool done[1 + maxn];
vector<int> ctree[1 + maxn];
int cpar[1 + maxn];
int croot;
int dep[1 + maxn];
int lift[1 + maxn][logn];
ll pref[1 + maxn];

int dfs_subtree(int cur, int par, const int &all_size) {
    int cur_size = 1;
    for(edge &nei : graph[cur]) {
        if(nei.to != par && !done[nei.to]) {
            int this_size = dfs_subtree(nei.to, cur, all_size);
            nei.subtree_size = this_size;
            cur_size += this_size;
        }
    }
    for(edge &nei : graph[cur]) {
        if(nei.to == par) {
            nei.subtree_size = all_size - cur_size;
            break;
        }
    }
    return cur_size;
}

void decompose(int cur, int prev_centroid, int all_size) {
    dfs_subtree(cur, -1, all_size);
    while(true) {
        pii best = mp(-1, all_size / 2);
        for(edge nei : graph[cur]) {
            if(!done[nei.to]) {
                pii cur_pair = mp(nei.to, nei.subtree_size);
                if(cur_pair.se > best.se) {
                    best = cur_pair;
                }
            }
        }
        /*cout << cur << " " << prev_centroid << " " << all_size << endl;
        for(edge e : graph[1]) {
            cout << e.to << " " << e.subtree_size << endl;
        }*/
        if(best.fi == -1) {
            break;
        }
        cur = best.fi;
    }
    // centroid: cur
    cpar[cur] = prev_centroid;
    if(prev_centroid != -1) {
        ctree[prev_centroid].pb(cur);
    } else {
        croot = cur;
    }
    done[cur] = true;
    for(edge nei : graph[cur]) {
        if(!done[nei.to]) {
            decompose(nei.to, cur, nei.subtree_size);
        }
    }
}

void dfs_depth(int cur) {
    for(edge nei : graph[cur]) {
        if(nei.to != lift[cur][0]) {
            lift[nei.to][0] = cur;
            dep[nei.to] = dep[cur] + 1;
            pref[nei.to] = pref[cur] + nei.wei;
            dfs_depth(nei.to);
        }
    }
}

int lca(int a, int b) {
    if(dep[a] > dep[b]) {
        swap(a, b);
    }
    for(int j = logn - 1; j >= 0; j--) {
        if(dep[b] - (1 << j) >= dep[a]) {
            b = lift[b][j];
        }
    }
    if(a == b) {
        return a;
    }
    for(int j = logn - 1; j >= 0; j--) {
        if(lift[a][j] != lift[b][j]) {
            a = lift[a][j];
            b = lift[b][j];
        }
    }
    return lift[b][0];
}

ll dist(int a, int b) {
    int c = lca(a, b);
    return pref[a] + pref[b] - 2 * pref[c];
}

ll nearest[1 + maxn];
bool to_reset[1 + maxn];
vector<int> reset;

void Init(signed N, signed A[], signed B[], signed D[]) {
    n = N;
    for(int i = 0; i < n - 1; i++) {
        int a = A[i], b = B[i], d = D[i];
        a++;
        b++;
        graph[a].pb(edge(b, d, 0));
        graph[b].pb(edge(a, d, 0));
    }
    /*for(int i = 1; i <= n; i++) {
        cout << i << endl;
        for(edge e : graph[i]) {
            cout << e.to << " " << e.wei << endl;
        }
    }
    return;*/
    decompose(1, -1, n);
    lift[1][0] = 1;
    dfs_depth(1);
    for(int j = 1; j < logn; j++) {
        for(int i = 1; i <= n; i++) {
            lift[i][j] = lift[lift[i][j - 1]][j - 1];
        }
    }
    for(int i = 1; i <= n; i++) {
        nearest[i] = inf;
    }
    /*for(int i = 1; i <= n; i++) {
        cout << cpar[i] << " ";
    }
    cout << endl;*/
}

void upd(int cur) {
    int centroid = cur;
    while(centroid != -1) {
        if(!to_reset[centroid]) {
            to_reset[centroid] = true;
            reset.pb(centroid);
        }
        nearest[centroid] = min(nearest[centroid], dist(centroid, cur));
        centroid = cpar[centroid];
    }
}

ll query(int cur) {
    int centroid = cur;
    ll res = inf;
    while(centroid != -1) {
        res = min(res, dist(centroid, cur) + nearest[centroid]);
        centroid = cpar[centroid];
    }
    return res;
}

ll Query(signed S, signed X[], signed T, signed Y[]) {
    vector<int> a, b;
    for(int i = 0; i < S; i++) {
        a.pb(X[i] + 1);
    }
    for(int j = 0; j < T; j++) {
        b.pb(Y[j] + 1);
    }
    for(int y : b) {
        upd(y);
    }
    ll ans = inf;
    for(int x : a) {
        ans = min(ans, query(x));
    }
    for(int r : reset) {
        to_reset[r] = false;
        nearest[r] = inf;
    }
    reset.clear();
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24412 KB Output is correct
2 Correct 511 ms 42580 KB Output is correct
3 Correct 1213 ms 42396 KB Output is correct
4 Correct 1132 ms 42320 KB Output is correct
5 Correct 1445 ms 42776 KB Output is correct
6 Correct 215 ms 42196 KB Output is correct
7 Correct 1222 ms 42320 KB Output is correct
8 Correct 1205 ms 42680 KB Output is correct
9 Correct 1426 ms 42716 KB Output is correct
10 Correct 216 ms 42324 KB Output is correct
11 Correct 1156 ms 42324 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24156 KB Output is correct
2 Correct 1594 ms 146856 KB Output is correct
3 Correct 3976 ms 149356 KB Output is correct
4 Correct 561 ms 138060 KB Output is correct
5 Correct 5910 ms 180580 KB Output is correct
6 Correct 4222 ms 151720 KB Output is correct
7 Correct 3365 ms 67368 KB Output is correct
8 Correct 330 ms 66040 KB Output is correct
9 Correct 4011 ms 72532 KB Output is correct
10 Correct 3404 ms 68780 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24412 KB Output is correct
2 Correct 511 ms 42580 KB Output is correct
3 Correct 1213 ms 42396 KB Output is correct
4 Correct 1132 ms 42320 KB Output is correct
5 Correct 1445 ms 42776 KB Output is correct
6 Correct 215 ms 42196 KB Output is correct
7 Correct 1222 ms 42320 KB Output is correct
8 Correct 1205 ms 42680 KB Output is correct
9 Correct 1426 ms 42716 KB Output is correct
10 Correct 216 ms 42324 KB Output is correct
11 Correct 1156 ms 42324 KB Output is correct
12 Correct 11 ms 24156 KB Output is correct
13 Correct 1594 ms 146856 KB Output is correct
14 Correct 3976 ms 149356 KB Output is correct
15 Correct 561 ms 138060 KB Output is correct
16 Correct 5910 ms 180580 KB Output is correct
17 Correct 4222 ms 151720 KB Output is correct
18 Correct 3365 ms 67368 KB Output is correct
19 Correct 330 ms 66040 KB Output is correct
20 Correct 4011 ms 72532 KB Output is correct
21 Correct 3404 ms 68780 KB Output is correct
22 Correct 2116 ms 154928 KB Output is correct
23 Correct 2261 ms 157292 KB Output is correct
24 Correct 6792 ms 158680 KB Output is correct
25 Correct 6706 ms 162092 KB Output is correct
26 Correct 6890 ms 157768 KB Output is correct
27 Execution timed out 8016 ms 182596 KB Time limit exceeded
28 Halted 0 ms 0 KB -