oj.uz

Submission #843470

# Submission time Handle Problem Language Result Execution time Memory
843470 2023-09-04T03:11:03 Z daoquanglinh2007 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 157580 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<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] + p;
        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 23 ms 43612 KB Output is correct
2 Correct 1347 ms 57576 KB Output is correct
3 Correct 1503 ms 57440 KB Output is correct
4 Correct 1485 ms 57684 KB Output is correct
5 Correct 1622 ms 57488 KB Output is correct
6 Correct 827 ms 56988 KB Output is correct
7 Correct 1489 ms 57536 KB Output is correct
8 Correct 1507 ms 57792 KB Output is correct
9 Correct 1578 ms 57452 KB Output is correct
10 Correct 827 ms 57036 KB Output is correct
11 Correct 1506 ms 57584 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 43612 KB Output is correct
2 Execution timed out 8025 ms 157580 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 43612 KB Output is correct
2 Correct 1347 ms 57576 KB Output is correct
3 Correct 1503 ms 57440 KB Output is correct
4 Correct 1485 ms 57684 KB Output is correct
5 Correct 1622 ms 57488 KB Output is correct
6 Correct 827 ms 56988 KB Output is correct
7 Correct 1489 ms 57536 KB Output is correct
8 Correct 1507 ms 57792 KB Output is correct
9 Correct 1578 ms 57452 KB Output is correct
10 Correct 827 ms 57036 KB Output is correct
11 Correct 1506 ms 57584 KB Output is correct
12 Correct 11 ms 43612 KB Output is correct
13 Execution timed out 8025 ms 157580 KB Time limit exceeded
14 Halted 0 ms 0 KB -