oj.uz

Submission #787295

# Submission time Handle Problem Language Result Execution time Memory
787295 2023-07-19T03:52:06 Z marvinthang Factories (JOI14_factories) C++17
100 / 100
 2335 ms 270408 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vii vector<pii>
#define isz(x) (int)x.size()
using namespace std;
 
const int mxN = 5e5 + 5;
const ll oo = 1e18;
 
int n;
vector<vii> G;
 
vi vtn;
vector<vector <pair <int, ll>>> vt;
 
ll dis[mxN];
pii sparse[20][mxN + mxN];
int timer, ecnt, ap[mxN], dep[mxN], cur[mxN], tin[mxN], tout[mxN];
 
void dfs(int v, int p) {
    tin[v] = ++timer;
    dep[v] = dep[p] + 1;
    sparse[0][++ecnt] = {dep[v], v};
    ap[v] = ecnt;
 
    for(auto &[u, w] : G[v]) {
        if(u == p) continue;
        dis[u] = dis[v] + w;
        dfs(u, v);
        sparse[0][++ecnt] = {dep[v], v};
    }
 
    tout[v] = ++timer;
}
 
void build_sparse() {
    for(int p = 1, i = 1; p << 1 <= ecnt; p <<= 1, ++i)
        for(int j = 1; j <= ecnt - (p << 1) + 1; ++j)
            sparse[i][j] = min(sparse[i - 1][j], sparse[i - 1][j + p]);
}
 
bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
 
int LCA(int u, int v) {
    int l = ap[u], r = ap[v];
    if(l > r) swap(l, r);
    int len = r - l + 1, lg_len = __lg(len);
    return min(sparse[lg_len][l], sparse[lg_len][r - (1 << lg_len) + 1]).ss;
}
 
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    G.resize(n); vt.resize(n);
    for(int i = 0; i < N - 1; ++i) {
        G[A[i]].emplace_back(B[i], D[i]);
        G[B[i]].emplace_back(A[i], D[i]);
    }
    dfs(0, 0); build_sparse();
}
 
long long Query(int S, int X[], int T, int Y[]) {
    queue<pii> q;
 
    for(int i = 0; i < S; ++i) {
        cur[X[i]] = 1;
        q.emplace(X[i], 0);
        vtn.emplace_back(X[i]);
    }
    for(int i = 0; i < T; ++i) {
        cur[Y[i]] = 2;
        vtn.emplace_back(Y[i]);
    }
 
    sort(all(vtn), [&](int u, int v) {
        return tin[u] < tin[v];
    });
 
    for(int i = 0; i < S + T - 1; ++i) vtn.emplace_back(LCA(vtn[i], vtn[i + 1]));

    sort(all(vtn), [&](int u, int v) {
        return tin[u] < tin[v];
    });
    vtn.erase(unique(all(vtn)), vtn.end());
 
    auto add_vt = [&](int u, int v, ll w) {
        vt[u].emplace_back(v, w);
        vt[v].emplace_back(u, w);
    };
 
    stack<int> s;
    for(int i = 0; i < isz(vtn); ++i) {
        while(not s.empty() && not is_ancestor(s.top(), vtn[i])) s.pop();
        if(s.empty()) s.emplace(vtn[i]);
        else {
            add_vt(s.top(), vtn[i], dis[vtn[i]] - dis[s.top()]);
            s.emplace(vtn[i]);
        }
    }
 
    ll res = oo;
 
    auto dfs = [&](auto self, int v, int p) -> vll {
        vll cur_dis(2, oo);
        if(cur[v]) cur_dis[cur[v] - 1] = 0;
        for(auto &[u, w] : vt[v]) {
            if(u == p) continue;
            vll tmp = self(self, u, v);
            for(int i = 0; i < 2; ++i)
                cur_dis[i] = min(cur_dis[i], tmp[i] + w);
        }
        res = min(res, accumulate(all(cur_dis), 0LL));
        return cur_dis;
    };
 
    dfs(dfs, vtn[0], 0);

    for (int u: vtn) {
        cur[u] = 0;
        vt[u].clear();
    }
    vtn.clear();
 
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 852 KB Output is correct
2 Correct 548 ms 10364 KB Output is correct
3 Correct 541 ms 10324 KB Output is correct
4 Correct 568 ms 10360 KB Output is correct
5 Correct 513 ms 10664 KB Output is correct
6 Correct 337 ms 10240 KB Output is correct
7 Correct 551 ms 10308 KB Output is correct
8 Correct 589 ms 10392 KB Output is correct
9 Correct 533 ms 10700 KB Output is correct
10 Correct 348 ms 10240 KB Output is correct
11 Correct 544 ms 10312 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 969 ms 231376 KB Output is correct
3 Correct 1008 ms 235780 KB Output is correct
4 Correct 782 ms 232752 KB Output is correct
5 Correct 955 ms 269264 KB Output is correct
6 Correct 1059 ms 237480 KB Output is correct
7 Correct 718 ms 66540 KB Output is correct
8 Correct 553 ms 66644 KB Output is correct
9 Correct 531 ms 71820 KB Output is correct
10 Correct 709 ms 67836 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 852 KB Output is correct
2 Correct 548 ms 10364 KB Output is correct
3 Correct 541 ms 10324 KB Output is correct
4 Correct 568 ms 10360 KB Output is correct
5 Correct 513 ms 10664 KB Output is correct
6 Correct 337 ms 10240 KB Output is correct
7 Correct 551 ms 10308 KB Output is correct
8 Correct 589 ms 10392 KB Output is correct
9 Correct 533 ms 10700 KB Output is correct
10 Correct 348 ms 10240 KB Output is correct
11 Correct 544 ms 10312 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 969 ms 231376 KB Output is correct
14 Correct 1008 ms 235780 KB Output is correct
15 Correct 782 ms 232752 KB Output is correct
16 Correct 955 ms 269264 KB Output is correct
17 Correct 1059 ms 237480 KB Output is correct
18 Correct 718 ms 66540 KB Output is correct
19 Correct 553 ms 66644 KB Output is correct
20 Correct 531 ms 71820 KB Output is correct
21 Correct 709 ms 67836 KB Output is correct
22 Correct 2118 ms 242956 KB Output is correct
23 Correct 1771 ms 243712 KB Output is correct
24 Correct 2335 ms 246908 KB Output is correct
25 Correct 2059 ms 250072 KB Output is correct
26 Correct 1942 ms 241492 KB Output is correct
27 Correct 2044 ms 270408 KB Output is correct
28 Correct 1556 ms 240456 KB Output is correct
29 Correct 1928 ms 240192 KB Output is correct
30 Correct 1914 ms 239380 KB Output is correct
31 Correct 1890 ms 240208 KB Output is correct
32 Correct 935 ms 76372 KB Output is correct
33 Correct 678 ms 69416 KB Output is correct
34 Correct 946 ms 65228 KB Output is correct
35 Correct 928 ms 65036 KB Output is correct
36 Correct 986 ms 65916 KB Output is correct
37 Correct 1006 ms 65776 KB Output is correct