Submission #768404

#	Time	Username	Problem	Language	Result	Execution time	Memory
768404		Abrar_Al_Samit	Factories (JOI14_factories)	C++17	100 / 100	5941 ms	174624 KiB

factories

#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 (stderr)

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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67