oj.uz

Submission #843523

# Submission time Handle Problem Language Result Execution time Memory
843523 2023-09-04T04:20:03 Z daoquanglinh2007 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 241300 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 = 1e6 + 5;
const ll oo = 1e18;

int n;
vector<vii> G;

vi vtn;
vector<vii> vt;

ll dis[mxN];
pii sparse[25][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() {
    assert(ecnt <= 2*n);
    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), res = min(sparse[lg_len][l], sparse[lg_len][r - (1 << lg_len) + 1]).ss;
    return res;
}

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, int 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] : G[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 < isz(vtn); i++){
        vt[vtn[i]].clear();
        cur[vtn[i]] = 0;
    }
    vtn.clear();

    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 43732 KB Output is correct
2 Correct 1405 ms 58704 KB Output is correct
3 Correct 1505 ms 58712 KB Output is correct
4 Correct 1471 ms 58784 KB Output is correct
5 Correct 1705 ms 59316 KB Output is correct
6 Correct 798 ms 58700 KB Output is correct
7 Correct 1482 ms 58716 KB Output is correct
8 Correct 1435 ms 59004 KB Output is correct
9 Correct 1621 ms 59332 KB Output is correct
10 Correct 779 ms 58820 KB Output is correct
11 Correct 1467 ms 58716 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 43608 KB Output is correct
2 Execution timed out 8096 ms 241300 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 43732 KB Output is correct
2 Correct 1405 ms 58704 KB Output is correct
3 Correct 1505 ms 58712 KB Output is correct
4 Correct 1471 ms 58784 KB Output is correct
5 Correct 1705 ms 59316 KB Output is correct
6 Correct 798 ms 58700 KB Output is correct
7 Correct 1482 ms 58716 KB Output is correct
8 Correct 1435 ms 59004 KB Output is correct
9 Correct 1621 ms 59332 KB Output is correct
10 Correct 779 ms 58820 KB Output is correct
11 Correct 1467 ms 58716 KB Output is correct
12 Correct 12 ms 43608 KB Output is correct
13 Execution timed out 8096 ms 241300 KB Time limit exceeded
14 Halted 0 ms 0 KB -