oj.uz

답안 #843454

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843454 2023-09-04T02:43:57 Z hotboy2703 공장들 (JOI14_factories) C++17
100 / 100
 2323 ms 490480 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<long long, long long>
#define vi vector<long long>
#define vll vector<ll>
#define vvi vector<vi>
#define vii vector<pii>
#define isz(x) (long long)x.size()
using namespace std;
//5e5
const long long mxN = 1e6 + 5;
const ll oo = 1e18;

long long n;
vector<vii> G;

vi vtn;
//vii -> vll
vector<vector <pair <long long,ll> > > vt;

ll dis[mxN];
//mxN
pii sparse[25][mxN * 2];
long long timer, ecnt, ap[mxN], dep[mxN], cur[mxN], tin[mxN], tout[mxN];

void dfs(long long v, long long p) {
    tin[v] = ++timer;
    dep[v] = dep[p] + 1;
    sparse[0][++ecnt] = {dep[v], v};
    ap[v] = ecnt;
    //dis
    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(long long p = 1, i = 1; p << 1 <= ecnt; p <<= 1, ++i)
        for(long long j = 1; j <= ecnt - (p << 1) + 1; ++j)
            sparse[i][j] = min(sparse[i - 1][j], sparse[i - 1][j + p]);
}

bool is_ancestor(long long u, long long v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

long long LCA(long long u, long long v) {
    long long l = ap[u], r = ap[v];
    if(l > r) swap(l, r);
    long long 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(long long i = 0; i < S; ++i) {
        cur[X[i]] = 1;
        q.emplace(X[i], 0);
        vtn.emplace_back(X[i]);
    }
    for(long long i = 0; i < T; ++i) {
        cur[Y[i]] = 2;
        vtn.emplace_back(Y[i]);
    }

    sort(all(vtn), [&](long long u, long long v) {
        return tin[u] < tin[v];
    });

    for(long long i = 0; i < S + T - 1; ++i) {
        vtn.emplace_back(LCA(vtn[i], vtn[i + 1]));
    }

    sort(all(vtn), [&](long long u, long long v) {
        return tin[u] < tin[v];
    });
    vtn.erase(unique(all(vtn)), vtn.end());

    auto add_vt = [&](long long u, long long v, long long w) {
        vt[u].emplace_back(v, w);
        vt[v].emplace_back(u, w);
    };

    stack<long long> s;
    for(long long 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, long long v, long long p) -> vll {
        vll cur_dis(2, oo);
        if(cur[v]) cur_dis[cur[v] - 1] = 0;
        //vt, G
        for(auto &[u, w] : vt[v]) {
            if(u == p) continue;
            //cout<<u<<' '<<v<<' '<<w<<' '<<dis[u]<<' '<<dis[v]<<'\n';
            vll tmp = self(self, u, v);
            for(long long 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(long long i = 0; i < S; ++i) {
        cur[X[i]] = 0;
        vt[X[i]].clear();
    }
    for(long long i = 0; i < T; ++i) {
        cur[Y[i]] = 0;
        vt[Y[i]].clear();
    }*/
    vtn.clear();

    return res;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 43608 KB Output is correct
2 Correct 548 ms 59300 KB Output is correct
3 Correct 564 ms 58836 KB Output is correct
4 Correct 576 ms 59012 KB Output is correct
5 Correct 540 ms 59204 KB Output is correct
6 Correct 353 ms 58820 KB Output is correct
7 Correct 543 ms 58700 KB Output is correct
8 Correct 547 ms 58828 KB Output is correct
9 Correct 508 ms 59152 KB Output is correct
10 Correct 455 ms 58804 KB Output is correct
11 Correct 571 ms 58708 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 43612 KB Output is correct
2 Correct 943 ms 456632 KB Output is correct
3 Correct 990 ms 462012 KB Output is correct
4 Correct 727 ms 453848 KB Output is correct
5 Correct 1179 ms 489992 KB Output is correct
6 Correct 1058 ms 462480 KB Output is correct
7 Correct 736 ms 137956 KB Output is correct
8 Correct 510 ms 136572 KB Output is correct
9 Correct 637 ms 142312 KB Output is correct
10 Correct 761 ms 138492 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 43608 KB Output is correct
2 Correct 548 ms 59300 KB Output is correct
3 Correct 564 ms 58836 KB Output is correct
4 Correct 576 ms 59012 KB Output is correct
5 Correct 540 ms 59204 KB Output is correct
6 Correct 353 ms 58820 KB Output is correct
7 Correct 543 ms 58700 KB Output is correct
8 Correct 547 ms 58828 KB Output is correct
9 Correct 508 ms 59152 KB Output is correct
10 Correct 455 ms 58804 KB Output is correct
11 Correct 571 ms 58708 KB Output is correct
12 Correct 6 ms 43612 KB Output is correct
13 Correct 943 ms 456632 KB Output is correct
14 Correct 990 ms 462012 KB Output is correct
15 Correct 727 ms 453848 KB Output is correct
16 Correct 1179 ms 489992 KB Output is correct
17 Correct 1058 ms 462480 KB Output is correct
18 Correct 736 ms 137956 KB Output is correct
19 Correct 510 ms 136572 KB Output is correct
20 Correct 637 ms 142312 KB Output is correct
21 Correct 761 ms 138492 KB Output is correct
22 Correct 2139 ms 466624 KB Output is correct
23 Correct 1752 ms 465780 KB Output is correct
24 Correct 2323 ms 470584 KB Output is correct
25 Correct 2226 ms 472572 KB Output is correct
26 Correct 1770 ms 464600 KB Output is correct
27 Correct 2170 ms 490480 KB Output is correct
28 Correct 1330 ms 460424 KB Output is correct
29 Correct 1570 ms 463216 KB Output is correct
30 Correct 1561 ms 462688 KB Output is correct
31 Correct 1532 ms 463184 KB Output is correct
32 Correct 969 ms 148532 KB Output is correct
33 Correct 623 ms 141768 KB Output is correct
34 Correct 914 ms 138336 KB Output is correct
35 Correct 874 ms 138064 KB Output is correct
36 Correct 958 ms 138892 KB Output is correct
37 Correct 926 ms 138724 KB Output is correct