oj.uz

Submission #843461

# Submission time Handle Problem Language Result Execution time Memory
843461 2023-09-04T02:56:33 Z hotboy2703 Factories (JOI14_factories) C++14
100 / 100
 1976 ms 283104 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, long long> > > vt;

ll dis[mxN];
pii sparse[20][mxN * 2];
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, long long 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;
        //cout<<v<<' '<<p<<'\n';
        for(auto &[u, w] : vt[v]) {
            if(u == p) continue;
            //cout<<v<<' '<<u<<' '<<w<<'\n';
            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 (auto x:vtn){
        cur[x] = 0;
        vt[x].clear();
    }
    /*for(int i = 0; i < S; ++i) {
        cur[X[i]] = 0;
        vt[X[i]].clear();
    }
    for(int i = 0; i < T; ++i) {
        cur[Y[i]] = 0;
        vt[Y[i]].clear();
    }*/
    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:122:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  122 |         for(auto &[u, w] : vt[v]) {
      |                   ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 45656 KB Output is correct
2 Correct 596 ms 58784 KB Output is correct
3 Correct 552 ms 58820 KB Output is correct
4 Correct 587 ms 58836 KB Output is correct
5 Correct 526 ms 59220 KB Output is correct
6 Correct 349 ms 58708 KB Output is correct
7 Correct 538 ms 58820 KB Output is correct
8 Correct 548 ms 58840 KB Output is correct
9 Correct 522 ms 58964 KB Output is correct
10 Correct 339 ms 58708 KB Output is correct
11 Correct 541 ms 58708 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 45656 KB Output is correct
2 Correct 850 ms 246208 KB Output is correct
3 Correct 874 ms 250980 KB Output is correct
4 Correct 678 ms 246716 KB Output is correct
5 Correct 847 ms 283104 KB Output is correct
6 Correct 923 ms 251988 KB Output is correct
7 Correct 661 ms 107456 KB Output is correct
8 Correct 472 ms 106548 KB Output is correct
9 Correct 523 ms 111700 KB Output is correct
10 Correct 678 ms 107888 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 45656 KB Output is correct
2 Correct 596 ms 58784 KB Output is correct
3 Correct 552 ms 58820 KB Output is correct
4 Correct 587 ms 58836 KB Output is correct
5 Correct 526 ms 59220 KB Output is correct
6 Correct 349 ms 58708 KB Output is correct
7 Correct 538 ms 58820 KB Output is correct
8 Correct 548 ms 58840 KB Output is correct
9 Correct 522 ms 58964 KB Output is correct
10 Correct 339 ms 58708 KB Output is correct
11 Correct 541 ms 58708 KB Output is correct
12 Correct 6 ms 45656 KB Output is correct
13 Correct 850 ms 246208 KB Output is correct
14 Correct 874 ms 250980 KB Output is correct
15 Correct 678 ms 246716 KB Output is correct
16 Correct 847 ms 283104 KB Output is correct
17 Correct 923 ms 251988 KB Output is correct
18 Correct 661 ms 107456 KB Output is correct
19 Correct 472 ms 106548 KB Output is correct
20 Correct 523 ms 111700 KB Output is correct
21 Correct 678 ms 107888 KB Output is correct
22 Correct 1976 ms 254484 KB Output is correct
23 Correct 1579 ms 253772 KB Output is correct
24 Correct 1968 ms 258668 KB Output is correct
25 Correct 1853 ms 260532 KB Output is correct
26 Correct 1604 ms 253468 KB Output is correct
27 Correct 1733 ms 280912 KB Output is correct
28 Correct 1227 ms 250668 KB Output is correct
29 Correct 1532 ms 252276 KB Output is correct
30 Correct 1554 ms 251436 KB Output is correct
31 Correct 1475 ms 252188 KB Output is correct
32 Correct 813 ms 116164 KB Output is correct
33 Correct 520 ms 109112 KB Output is correct
34 Correct 872 ms 107212 KB Output is correct
35 Correct 802 ms 107168 KB Output is correct
36 Correct 903 ms 107976 KB Output is correct
37 Correct 849 ms 107924 KB Output is correct