oj.uz

Submission #843379

# Submission time Handle Problem Language Result Execution time Memory
843379 2023-09-04T01:16:58 Z TranGiaHuy1508 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 152884 KB 
// Credit: CDuongg

#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<vii> vt;
 
ll dis[mxN];
pii sparse[19][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, 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 < 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;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 45656 KB Output is correct
2 Correct 1328 ms 57424 KB Output is correct
3 Correct 1497 ms 57804 KB Output is correct
4 Correct 1510 ms 57992 KB Output is correct
5 Correct 1629 ms 57480 KB Output is correct
6 Correct 793 ms 57172 KB Output is correct
7 Correct 1480 ms 57536 KB Output is correct
8 Correct 1471 ms 57588 KB Output is correct
9 Correct 1595 ms 57496 KB Output is correct
10 Correct 797 ms 57172 KB Output is correct
11 Correct 1479 ms 57432 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 45656 KB Output is correct
2 Correct 1328 ms 57424 KB Output is correct
3 Correct 1497 ms 57804 KB Output is correct
4 Correct 1510 ms 57992 KB Output is correct
5 Correct 1629 ms 57480 KB Output is correct
6 Correct 793 ms 57172 KB Output is correct
7 Correct 1480 ms 57536 KB Output is correct
8 Correct 1471 ms 57588 KB Output is correct
9 Correct 1595 ms 57496 KB Output is correct
10 Correct 797 ms 57172 KB Output is correct
11 Correct 1479 ms 57432 KB Output is correct
12 Correct 12 ms 45656 KB Output is correct
13 Execution timed out 8029 ms 152884 KB Time limit exceeded
14 Halted 0 ms 0 KB -