oj.uz

Submission #843579

# Submission time Handle Problem Language Result Execution time Memory
843579 2023-09-04T07:05:57 Z Thanhs Factories (JOI14_factories) C++14
100 / 100
 2127 ms 292284 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<vector<pair<int,ll>>> G;
 
vi vtn;
vector<vector<pair<int,ll>>> vt;
 
ll dis[mxN];
pii sparse[25][2*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[]) {
    for(int i = 0; i < S; ++i) {
        cur[X[i]] = 1;
        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 i=0;i<(int)(vtn.size());++i) vt[vtn[i]].clear();
    for(int i = 0; i < S; ++i) cur[X[i]] = 0;
    for(int i = 0; i < T; ++i) cur[Y[i]] = 0;
    vtn.clear();
 
    return res;
}

Compilation message

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:38:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |     for(auto &[u, w] : G[v]) {
      |               ^
factories.cpp: In lambda function:
factories.cpp:118:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |         for(auto &[u, w] : vt[v]) {
      |                   ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 43864 KB Output is correct
2 Correct 561 ms 56792 KB Output is correct
3 Correct 557 ms 56776 KB Output is correct
4 Correct 556 ms 56780 KB Output is correct
5 Correct 543 ms 57180 KB Output is correct
6 Correct 342 ms 56764 KB Output is correct
7 Correct 543 ms 56812 KB Output is correct
8 Correct 550 ms 57032 KB Output is correct
9 Correct 523 ms 57180 KB Output is correct
10 Correct 359 ms 56728 KB Output is correct
11 Correct 555 ms 57020 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 43608 KB Output is correct
2 Correct 913 ms 253260 KB Output is correct
3 Correct 947 ms 258532 KB Output is correct
4 Correct 738 ms 250680 KB Output is correct
5 Correct 926 ms 292284 KB Output is correct
6 Correct 1082 ms 258804 KB Output is correct
7 Correct 711 ms 107708 KB Output is correct
8 Correct 514 ms 106180 KB Output is correct
9 Correct 522 ms 112724 KB Output is correct
10 Correct 688 ms 108112 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 43864 KB Output is correct
2 Correct 561 ms 56792 KB Output is correct
3 Correct 557 ms 56776 KB Output is correct
4 Correct 556 ms 56780 KB Output is correct
5 Correct 543 ms 57180 KB Output is correct
6 Correct 342 ms 56764 KB Output is correct
7 Correct 543 ms 56812 KB Output is correct
8 Correct 550 ms 57032 KB Output is correct
9 Correct 523 ms 57180 KB Output is correct
10 Correct 359 ms 56728 KB Output is correct
11 Correct 555 ms 57020 KB Output is correct
12 Correct 6 ms 43608 KB Output is correct
13 Correct 913 ms 253260 KB Output is correct
14 Correct 947 ms 258532 KB Output is correct
15 Correct 738 ms 250680 KB Output is correct
16 Correct 926 ms 292284 KB Output is correct
17 Correct 1082 ms 258804 KB Output is correct
18 Correct 711 ms 107708 KB Output is correct
19 Correct 514 ms 106180 KB Output is correct
20 Correct 522 ms 112724 KB Output is correct
21 Correct 688 ms 108112 KB Output is correct
22 Correct 2055 ms 261320 KB Output is correct
23 Correct 1661 ms 260844 KB Output is correct
24 Correct 2110 ms 265668 KB Output is correct
25 Correct 2025 ms 267460 KB Output is correct
26 Correct 1700 ms 261196 KB Output is correct
27 Correct 2127 ms 289968 KB Output is correct
28 Correct 1290 ms 254896 KB Output is correct
29 Correct 1625 ms 259440 KB Output is correct
30 Correct 1647 ms 258880 KB Output is correct
31 Correct 1586 ms 259960 KB Output is correct
32 Correct 890 ms 116388 KB Output is correct
33 Correct 548 ms 109248 KB Output is correct
34 Correct 884 ms 107604 KB Output is correct
35 Correct 841 ms 107396 KB Output is correct
36 Correct 890 ms 108468 KB Output is correct
37 Correct 898 ms 108108 KB Output is correct