oj.uz

답안 #367514

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
367514 2021-02-17T14:37:50 Z mihai145 공장들 (JOI14_factories) C++14
100 / 100
 5919 ms 218992 KB 
#include "factories.h"
#include <vector>
//#include <iostream>
#include <algorithm>
#include <set>
#include <stack>

using namespace std;

const int NMAX = 500000;
const int LGMAX = 19;

const long long INF = 1e18;

vector<pair<int, int> > g[NMAX + 5];

long long dist[NMAX + 5];
int lvl[NMAX + 5];

int firstAp[NMAX + 2];
vector<int> rmq[LGMAX + 2];

int log2[2 * NMAX + 2];

void dfs(int node, int parent = -1) {

    firstAp[node] = (int) rmq[0].size();
    rmq[0].push_back(node);

    for (auto it : g[node]) {
        if (it.first != parent) {
            lvl[it.first] = lvl[node] + 1;
            dist[it.first] = dist[node] + it.second;
            dfs(it.first, node);
            rmq[0].push_back(node);
        }
    }
}

int GetMinLvl(int A, int B) {
    if (lvl[A] < lvl[B]) {
        return A;
    }

    return B;
}

void BuildRmq() {

    log2[1] = 0;
    for (int i = 2; i <= 2 * NMAX; i++) {
        log2[i] = log2[i / 2] + 1;
    }

    for (int i = 1; i <= LGMAX; i++) {
        if ((1 << i) > (int) rmq[0].size()) {
            break;
        } else {
            for (int j = 0; j < (int) rmq[0].size(); j++) {
                if (j + (1 << i) > (int) rmq[0].size()) {
                    break;
                } else {
                    rmq[i].push_back(GetMinLvl(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]));
                }
            }
        }
    }
}

int LCA(int A, int B) {
    A = firstAp[A];
    B = firstAp[B];

    if (A > B)
        swap(A, B);

    int k = log2[B - A + 1];
    return GetMinLvl(rmq[k][A], rmq[k][B - (1 << k) + 1]);
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 1; i < N; i++) {
        g[A[i - 1]].push_back({B[i - 1], D[i - 1]});
        g[B[i - 1]].push_back({A[i - 1], D[i - 1]});
    }

    dfs(0);
    BuildRmq();
}

vector<pair<int, long long>> g2[NMAX + 2];
long long dp1[NMAX + 2], dp2[NMAX + 2];

void computeDp1(int node, int parent = -1) {
    for (auto it : g2[node]) {
        if (it.first != parent) {
            computeDp1(it.first, node);
            dp1[node] = min(dp1[node], it.second + dp1[it.first]);
        }
    }
}

void computeDp2(int node, int parent = -1) {
    dp2[node] = min(dp1[node], dp2[node]);

    for (auto it : g2[node]) {
        if (it.first != parent) {
            dp2[it.first] = min(dp2[it.first], it.second + dp2[node]);
            computeDp2(it.first, node);
        }
    }
}

bool isAncestor(int A, int B) {
    return (A == LCA(A, B));
}

long long GetDist(int A, int B) {
    return dist[A] + dist[B] - 2 * dist[LCA(A, B)];
}

long long Solve(vector<int> &base, vector<int> &red, vector<int> &blue) {
    for (auto it : base) {
        g2[it].clear();
        dp1[it] = dp2[it] = INF;
    }

    for (auto it : red) {
        dp1[it] = 0;
    }

    stack<int> st;
    for (auto vert : base) {
        while (!st.empty() && isAncestor(st.top(), vert) == false) {
            st.pop();
        }

        if (!st.empty()) {
            long long dist = GetDist(st.top(), vert);
            g2[st.top()].push_back({vert, dist});
            g2[vert].push_back({st.top(), dist});
        }

        st.push(vert);
    }

    computeDp1(base[0]);
    computeDp2(base[0]);

    long long ans = INF;
    for (auto it : blue) {
        ans = min(ans, dp2[it]);
    }

    return ans;
}

inline bool cmp(const int A, const int B) {
    return firstAp[A] < firstAp[B];
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<int> base;
    for (int i = 0; i < S; i++)
        base.push_back(X[i]);
    for (int i = 0; i < T; i++)
        base.push_back(Y[i]);

    sort(base.begin(), base.end(), cmp);

    vector<int> aux = base;
    for (int i = 1; i < (int) base.size(); i++)
        aux.push_back(LCA(base[i - 1], base[i]));

    set<int> vertices;
    for (auto it : aux)
        vertices.insert(it);
    base.clear();
    for (auto it : vertices)
        base.push_back(it);

    sort(base.begin(), base.end(), cmp);

    vector<int> red, blue;
    for (int i = 0; i < S; i++)
        red.push_back(X[i]);
    for (int i = 0; i < T; i++)
        blue.push_back(Y[i]);

    return Solve(base, red, blue);
}

Compilation message

factories.cpp:23:5: warning: built-in function 'log2' declared as non-function [-Wbuiltin-declaration-mismatch]
   23 | int log2[2 * NMAX + 2];
      |     ^~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 28268 KB Output is correct
2 Correct 1652 ms 37356 KB Output is correct
3 Correct 1779 ms 37100 KB Output is correct
4 Correct 1661 ms 37736 KB Output is correct
5 Correct 1430 ms 47084 KB Output is correct
6 Correct 1221 ms 46976 KB Output is correct
7 Correct 1765 ms 46488 KB Output is correct
8 Correct 1661 ms 46828 KB Output is correct
9 Correct 1425 ms 47084 KB Output is correct
10 Correct 1225 ms 46700 KB Output is correct
11 Correct 1768 ms 46828 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 28012 KB Output is correct
2 Correct 2259 ms 163400 KB Output is correct
3 Correct 2496 ms 167060 KB Output is correct
4 Correct 1806 ms 182140 KB Output is correct
5 Correct 2169 ms 218992 KB Output is correct
6 Correct 2741 ms 187340 KB Output is correct
7 Correct 2611 ms 76876 KB Output is correct
8 Correct 1594 ms 76564 KB Output is correct
9 Correct 1635 ms 81764 KB Output is correct
10 Correct 2544 ms 78016 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 28268 KB Output is correct
2 Correct 1652 ms 37356 KB Output is correct
3 Correct 1779 ms 37100 KB Output is correct
4 Correct 1661 ms 37736 KB Output is correct
5 Correct 1430 ms 47084 KB Output is correct
6 Correct 1221 ms 46976 KB Output is correct
7 Correct 1765 ms 46488 KB Output is correct
8 Correct 1661 ms 46828 KB Output is correct
9 Correct 1425 ms 47084 KB Output is correct
10 Correct 1225 ms 46700 KB Output is correct
11 Correct 1768 ms 46828 KB Output is correct
12 Correct 23 ms 28012 KB Output is correct
13 Correct 2259 ms 163400 KB Output is correct
14 Correct 2496 ms 167060 KB Output is correct
15 Correct 1806 ms 182140 KB Output is correct
16 Correct 2169 ms 218992 KB Output is correct
17 Correct 2741 ms 187340 KB Output is correct
18 Correct 2611 ms 76876 KB Output is correct
19 Correct 1594 ms 76564 KB Output is correct
20 Correct 1635 ms 81764 KB Output is correct
21 Correct 2544 ms 78016 KB Output is correct
22 Correct 5224 ms 184040 KB Output is correct
23 Correct 4386 ms 183332 KB Output is correct
24 Correct 5919 ms 189532 KB Output is correct
25 Correct 5468 ms 192484 KB Output is correct
26 Correct 5600 ms 178656 KB Output is correct
27 Correct 4603 ms 209616 KB Output is correct
28 Correct 3345 ms 181384 KB Output is correct
29 Correct 5206 ms 177080 KB Output is correct
30 Correct 5109 ms 176712 KB Output is correct
31 Correct 5093 ms 177556 KB Output is correct
32 Correct 2585 ms 88444 KB Output is correct
33 Correct 2023 ms 84312 KB Output is correct
34 Correct 3079 ms 75652 KB Output is correct
35 Correct 3024 ms 75380 KB Output is correct
36 Correct 3389 ms 76252 KB Output is correct
37 Correct 3329 ms 76080 KB Output is correct