oj.uz

Submission #768404

# Submission time Handle Problem Language Result Execution time Memory
768404 2023-06-28T05:28:12 Z Abrar_Al_Samit Factories (JOI14_factories) C++17
100 / 100
 5941 ms 174624 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

const int nax = 5e5 + 3;
const int lg = 20;

vector<pair<int, int>>g[nax];

int st[nax], en[nax], tt = 0;
int up[nax][lg];
long long d[nax];

void dfs(int v, int p) {
    st[v] = tt++;
    up[v][0] = p;

    for(int j=1; j<lg; ++j) {
        up[v][j] = up[up[v][j-1]][j-1];
    }

    for(auto [u, w] : g[v]) if(u!=p) {
        d[u] = d[v] + w;
        dfs(u, v);
    }
    en[v] = tt-1;
}

bool is_anc(int u, int v) {
    return st[u]<=st[v] && en[u]>=en[v];
}
int getLCA(int u, int v) {
    for(int j=lg-1; j>=0; --j) if(!is_anc(up[u][j], v)) {
        u = up[u][j];
    }
    if(!is_anc(u, v)) u = up[u][0];
    return u;
}
long long get_dist(int u, int v) {
    int lca = getLCA(u, v);
    return d[u] + d[v] - 2 * d[lca];
}
long long d1[nax], d2[nax];
void Init(int N, int A[], int B[], int D[]) {
    for(int i=0; i+1<N; ++i) {
        g[A[i]].emplace_back(B[i], D[i]);
        g[B[i]].emplace_back(A[i], D[i]);
    }

    dfs(0, 0);
    for(int i=0; i<N; ++i) {
        d1[i] = d2[i] = 1e18;
    }
}

int type[nax];
vector<int>vt[nax];
long long ans;

void dfsvt(int v) {
    if(type[v]&1) d1[v] = 0;
    if(type[v]&2) d2[v] = 0;

    for(int u : vt[v]) {
        dfsvt(u);

        d1[v] = min(d1[v], d1[u]+get_dist(u, v));
        d2[v] = min(d2[v], d2[u]+get_dist(u, v));
    }
    ans = min(ans, d1[v] + d2[v]);
}
long long Query(int S, int X[], int T, int Y[]) {
    vector<int>nodes;
    for(int i=0; i<S; ++i) {
        nodes.push_back(X[i]);
        type[X[i]] |= 1;
    }
    for(int i=0; i<T; ++i) {
        if(!type[Y[i]]) nodes.push_back(Y[i]);
        type[Y[i]] |= 2;
    }

    sort(nodes.begin(), nodes.end(), [&] (int x, int y) {
        return st[x]<st[y];
    });


    vector<int>lcas;
    for(int i=0; i+1<nodes.size(); ++i) {
        int cur_lca = getLCA(nodes[i], nodes[i+1]);
        if(!type[cur_lca]) lcas.push_back(cur_lca);
    }

    sort(lcas.begin(), lcas.end());
    lcas.resize(unique(lcas.begin(), lcas.end())-lcas.begin());

    for(int x : lcas) {
        nodes.push_back(x);
    }

    sort(nodes.begin(), nodes.end(), [&] (int x, int y) {
        return st[x]<st[y];
    });



    stack<int>st;
    for(int x : nodes) {
        while(!st.empty() && !is_anc(st.top(), x)) {
            st.pop();
        }
        if(!st.empty()) {
            vt[st.top()].push_back(x);
        }
        st.push(x);
    }

    int root = nodes[0];
    ans = 1e18;
    dfsvt(root);

    for(int x : nodes) {
        vt[x].clear();
        d1[x] = d2[x] = 1e18;
        type[x] = 0;
    }
    return ans;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:90:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i=0; i+1<nodes.size(); ++i) {
      |                  ~~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 24276 KB Output is correct
2 Correct 1270 ms 42128 KB Output is correct
3 Correct 1530 ms 42292 KB Output is correct
4 Correct 1322 ms 42224 KB Output is correct
5 Correct 1090 ms 42468 KB Output is correct
6 Correct 1018 ms 42152 KB Output is correct
7 Correct 1487 ms 42268 KB Output is correct
8 Correct 1349 ms 42320 KB Output is correct
9 Correct 1086 ms 42580 KB Output is correct
10 Correct 994 ms 42108 KB Output is correct
11 Correct 1526 ms 42188 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24020 KB Output is correct
2 Correct 1654 ms 112972 KB Output is correct
3 Correct 3303 ms 116108 KB Output is correct
4 Correct 1263 ms 127104 KB Output is correct
5 Correct 3287 ms 165904 KB Output is correct
6 Correct 3688 ms 116992 KB Output is correct
7 Correct 2908 ms 63468 KB Output is correct
8 Correct 1182 ms 63516 KB Output is correct
9 Correct 2414 ms 69460 KB Output is correct
10 Correct 2832 ms 64492 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 24276 KB Output is correct
2 Correct 1270 ms 42128 KB Output is correct
3 Correct 1530 ms 42292 KB Output is correct
4 Correct 1322 ms 42224 KB Output is correct
5 Correct 1090 ms 42468 KB Output is correct
6 Correct 1018 ms 42152 KB Output is correct
7 Correct 1487 ms 42268 KB Output is correct
8 Correct 1349 ms 42320 KB Output is correct
9 Correct 1086 ms 42580 KB Output is correct
10 Correct 994 ms 42108 KB Output is correct
11 Correct 1526 ms 42188 KB Output is correct
12 Correct 19 ms 24020 KB Output is correct
13 Correct 1654 ms 112972 KB Output is correct
14 Correct 3303 ms 116108 KB Output is correct
15 Correct 1263 ms 127104 KB Output is correct
16 Correct 3287 ms 165904 KB Output is correct
17 Correct 3688 ms 116992 KB Output is correct
18 Correct 2908 ms 63468 KB Output is correct
19 Correct 1182 ms 63516 KB Output is correct
20 Correct 2414 ms 69460 KB Output is correct
21 Correct 2832 ms 64492 KB Output is correct
22 Correct 3791 ms 143916 KB Output is correct
23 Correct 3285 ms 145424 KB Output is correct
24 Correct 4963 ms 148420 KB Output is correct
25 Correct 4761 ms 151416 KB Output is correct
26 Correct 5557 ms 143164 KB Output is correct
27 Correct 4508 ms 174624 KB Output is correct
28 Correct 2294 ms 143168 KB Output is correct
29 Correct 5787 ms 142028 KB Output is correct
30 Correct 5663 ms 139456 KB Output is correct
31 Correct 5941 ms 141828 KB Output is correct
32 Correct 2140 ms 72432 KB Output is correct
33 Correct 1398 ms 66452 KB Output is correct
34 Correct 1942 ms 62756 KB Output is correct
35 Correct 1910 ms 62596 KB Output is correct
36 Correct 2704 ms 63440 KB Output is correct
37 Correct 2708 ms 63256 KB Output is correct