제출 #468651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
468651		blue	공장들 (JOI14_factories)	C++17	컴파일 에러	0 ms	0 KiB

factories

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

const int maxN = 500'000;
const int logN = 20;
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);
int** anc;

void tle_assert(bool b)
{
    if(!b) while(1);
}

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;
        anc[v][0] = u;

        dfs(v);
    }
}

void Init(int N_, int A[], int B[], int D[])
{
    N = N_;

    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] );
    }

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

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

    for(int e = 1; e < logN; e++)
        for(int i = 0; i < N; i++)
            anc[i][e] = anc[ anc[i][e-1] ][e-1];
}

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

    return u;
}

int lca(int u, int v)
{
    assert(1 <= u && u <= N);
    assert(1 <= v && v <= N);
    if(depth[u] > depth[v]) swap(u, v);

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

    if(u == v) return u;

    for(int e = logN-1; e >= 0; e--)
    {
        if(anc[u][e] != anc[v][e])
        {
            u = anc[u][e];
            v = anc[v][e];
        }
    }
    u = anc[u][0];
    v = anc[v][0];
    return u;
}

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

vector<int>* new_edge;
vector<long long>* new_wt;

int act(int i) //actual
{
    tle_assert(0 <= i && i < S+T+int(Z.size()));
    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);

    tle_assert(0 <= u && u < S + T + int(Z.size()));
    tle_assert(0 <= v && v < S + T + int(Z.size()));
}


vector<long long> src_dist;

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];

    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();

    new_edge = new vector<int>[Q];
    new_wt = new vector<long long>[Q];


    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]);
    }


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

    set<pos> tbv;
    for(int i = 0; i < Q; i++) tbv.insert(pos{i});

    while(!tbv.empty())
    {
        int u = tbv.begin()->i;
        tbv.erase(tbv.begin());

        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)
            {
                tbv.erase(pos{v});
                src_dist[v] = src_dist[u] + w;
                tbv.insert(pos{v});
            }
        }
    }

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

    return res;
}

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp: In function 'int lca(int, int)':
factories.cpp:86:5: error: 'assert' was not declared in this scope
   86 |     assert(1 <= u && u <= N);
      |     ^~~~~~
factories.cpp:6:1: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
    5 | #include <algorithm>
  +++ |+#include <cassert>
    6 | using namespace std;