제출 #468669

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
468669		blue	공장들 (JOI14_factories)	C++17	100 / 100	7470 ms	255968 KiB

factories

#include "factories.h"
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

const int maxN = 500'000;
const int logN = 21;
const long long INF = 1'000'000'000'000'000'000LL;

//ZERO-INDEXED!!!

int N;
vector<int> edge[maxN];
vector<long long> wt[maxN];

int curr = -1;
vector<int> order;
vector<int> ind(maxN, -1);
vector<int> depth(maxN, 0);
vector<long long> dist0(maxN, 0);
vector<int> parent(maxN);
int** anc;

vector<int> lg2(1+maxN);

void dfs(int u)
{
    curr++;
    ind[u] = curr;
    order.push_back(u);

    for(int e = 0; e < (int)edge[u].size(); e++)
    {
        int v = edge[u][e];
        long long w = wt[u][e];

        if(ind[v] != -1) continue;

        depth[v] = depth[u] + 1;
        dist0[v] = dist0[u] + w;
        parent[v] = u;

        dfs(v);
    }
}

int access_anc(int u, int e)
{
    if(e >= lg2[depth[u]]) return 0;
    else return anc[u][e];
}

void Init(int N_, int A[], int B[], int D[])
{
    N = N_;
    lg2[0] = 1;
    lg2[1] = 1;
    for(int i = 1; i <= N; i++) lg2[i] = 1 + lg2[i/2];

    for(int e = 0; e < N-1; e++)
    {
        edge[ A[e] ].push_back( B[e] );
        wt[ A[e] ].push_back( D[e] );

        edge[ B[e] ].push_back( A[e] );
        wt[ B[e] ].push_back( D[e] );
    }

    parent[0] = 0;
    dfs(0);

    // cerr << "dfs done\n";

    anc = new int*[N];
    for(int i = 0; i < N; i++) anc[i] = new int[lg2[depth[i]]];

    for(int i = 0; i < N; i++) anc[i][0] = parent[i];

    // cerr << "check 1\n";

    for(int e = 1; e < logN; e++)
    {
        // cerr << "e = " << e << '\n';
        for(int i = 0; i < N; i++)
        {
            // cerr << "i = " << i << '\n';
            if(e < lg2[depth[i]])
            {
                // cerr << "case X\n";
                anc[i][e] = access_anc( access_anc(i, e-1) , e-1);
            }
        }
    }
    // cerr << "check 2\n";
}

int getAnc(int u, int d)
{
    for(int e = logN-1; e >= 0; e--)
        if((1 << e) & d)
            u = access_anc(u, e);

    return u;
}

int lca(int u, int v)
{
    if(depth[u] > depth[v]) swap(u, v);

    for(int e = logN-1; e >= 0; e--)
        if((1 << e) & (depth[v] - depth[u]))
            v = access_anc(v, e);

    if(u == v) return u;

    for(int e = logN-1; e >= 0; e--)
    {
        if(access_anc(u, e) != access_anc(v, e))
        {
            u = access_anc(u, e);
            v = access_anc(v, e);
        }
    }
    u = access_anc(u, 0);
    v = access_anc(v, 0);
    return u;
}

int S;
int* X;
int T;
int* Y;
vector<int> Z;

vector<int> new_edge[1'200'000];
vector<long long> new_wt[1'200'000];

int act(int i) //actual
{
    if(i < S) return X[i];
    else if(i < S+T) return Y[i-S];
    else return Z[i-S-T];
}

void add_new_edge(int u, int v, long long d)
{
    new_edge[u].push_back(v);
    new_wt[u].push_back(d);

    new_edge[v].push_back(u);
    new_wt[v].push_back(d);
}


vector<long long> src_dist(1'200'000);

struct pos
{
    int i;
};

bool operator < (pos A, pos B)
{
    if(src_dist[A.i] == src_dist[B.i]) return A.i < B.i;
    return src_dist[A.i] < src_dist[B.i];
}





long long Query(int S_, int X_[], int T_, int Y_[])
{
    S = S_;
    T = T_;

    // X = vector<int>(S);
    // for(int i = 0; i < S; i++) X[i] = X_[i];

    // Y = vector<int>(T);
    // for(int i = 0; i < T; i++) Y[i] = Y_[i];

    X = X_;
    Y = Y_;

    Z.clear();


    vector<int> V(S+T);
    for(int i = 0; i < S+T; i++) V[i] = i;
    sort(V.begin(), V.end(), [] (int i, int j)
    {
        return ind[act(i)] < ind[act(j)];
    });


    for(int i = 0; i+1 < S+T; i++)
    {
        Z.push_back(lca(act(V[i]), act(V[i+1])));
        V.push_back(S+T+i);
    }
    sort(V.begin(), V.end(), [] (int i, int j)
    {
        return ind[act(i)] < ind[act(j)];
    });

    int Q = (int)V.size();


    vector<int> st(1, V[0]);
    for(int i = 1; i < Q; i++)
    {
        while(act(st.back()) != getAnc(act(V[i]), depth[act(V[i])] - depth[act(st.back())]))
            st.pop_back();

        add_new_edge(V[i], st.back(), dist0[act(V[i])] - dist0[act(st.back())]);

        st.push_back(V[i]);
    }


    for(int i = 0; i < S; i++) src_dist[i] = 0;
    for(int i = S; i < Q; i++) src_dist[i] = INF;

    queue<pos> tbv;
    for(int i = 0; i < S; i++) tbv.push(pos{i});

    while(!tbv.empty())
    {
        int u = tbv.front().i;
        tbv.pop();

        for(int e = 0; e < (int)new_edge[u].size(); e++)
        {
            int v = new_edge[u][e];
            long long w = new_wt[u][e];
            if(src_dist[v] > src_dist[u] + w)
            {
                src_dist[v] = src_dist[u] + w;
                tbv.push(pos{v});
            }
        }
    }

    long long res = INF;
    for(int i = S; i < S+T; i++)
        res = min(res, src_dist[i]);


    // X.clear();
    // Y.clear();
    Z.clear();
    for(int i = 0; i < Q; i++)
    {
        new_edge[i].clear();
        new_wt[i].clear();
    }

    return res;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67