Submission #1266465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266465		trinm01	공장들 (JOI14_factories)	C++20	Compilation error	0 ms	0 KiB

factories

// #pragma GCC optimize("O3")
// #pragma GCC optimization("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>

const ll mod = 1e9 + 7;
const int MAXN = 5e5 + 5;
const ll oo = 1e18+7;  
const int base = 0;

int n, qq;
vector<pii> adj[MAXN];

int d[MAXN], up[MAXN][20], h[MAXN], in[MAXN], out[MAXN], cnt;
void dfs(int u, int p){
    in[u]=out[u]=++cnt;
    for(auto [v, w]:adj[u]){
        if(v==p) continue;
        d[v]=d[u]+w;
        h[v]=h[u]+1;
        up[v][0]=u;
        FOR(i, 1, 19){
            up[v][i]=up[up[v][i-1]][i-1];
        }
        dfs(v, u);
        out[u]=max(out[u], out[v]);
    }
}

int lca(int u, int v){
    if(h[u]!=h[v]){
        if(h[u]<h[v]) swap(u, v);
        int k=h[u]-h[v];
        FOR(i, 0, 19){
            if((k>>i)&1){
                u=up[u][i];
            }
        }
    }
    if(u==v) return u;
    FOD(i, 19, 0){
        if(up[u][i]!=up[v][i]){
            u=up[u][i];
            v=up[v][i];
        }
    }
    return up[u][0];
}

int dist(int u, int v){
    return d[u]+d[v]-2*d[lca(u, v)];
}

bool cmp(int u, int v){
    return in[u]<in[v];
}

bool inside(int u, int v){
    if(in[u]<=in[v] && out[u]>=out[v]){
        return 1;
    }
    return 0;
}

vector<pii> adj1[MAXN];

int f[MAXN];
void dijsktra(vector<int> &a, vector<int> &b){
    priority_queue<pii, vector<pii>, greater<pii>> q;
    for(auto x:b){
        f[x]=oo;
    }
    for(auto x:a){
        f[x]=0;
        q.push({0, x});
    }

    while(!q.empty()){
        auto [c, u]=q.top();
        q.pop();
        if(c>f[u]) continue;
        for(auto [v, w]:adj1[u]){
            if(f[v]>f[u]+w){
                f[v]=f[u]+w;
                q.push({f[v], v});
            }
        }
    }
}

int solve(int p, int q, vector<int> &a, vector<int> &b){
    vector<int> vec;
    for(auto x:a){
        vec.push_back(x);
    }
    for(auto x:b){
        vec.push_back(x);
    }
    sort(vec.begin(), vec.end(), cmp);
    FOR(i, 1, p+q-1){
        vec.push_back(lca(vec[i], vec[i-1]));
    }
    sort(vec.begin(), vec.end(), cmp);
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    stack<int> st;
    st.push(vec[0]);
    // cout << vec[0] << ' ';
    FOR(i, 1, vec.size()-1){
        while(!inside(st.top(), vec[i])){
            st.pop();
        }
        adj1[st.top()].push_back({vec[i], dist(st.top(), vec[i])});
        adj1[vec[i]].push_back({st.top(), dist(st.top(), vec[i])});
        // cout << st.top() << ' ' << vec[i] << ' ' << dist(st.top(), vec[i]) << '\n';
        st.push(vec[i]);
        // cout << vec[i] << ' ';
    }

    dijsktra(a, vec);
    int ans=oo;
    for(auto x:b){
        ans=min(ans, f[x]);
    }
    
    for(auto x:vec){
        adj[x].clear();
    }

    return ans;
    
}

void Init(int N, int A[], int B[], int D[]){
    n=N;
    FOR(i, 0, n-1){
        adj[i].clear();
    }
    FOR(i, 0, n-2){
        int u, v, c;
        u=A[i], v=B[i], c=D[i];
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }
    cnt=0;

    dfs(0, -1);

    return;
}


long long Query(int S, int X[], int T, int Y[]){
    int p=S, q=T;
    vector<int> a, b;
    FOR(i, 0, S-1){
        a.push_back(X[i]);
    }
    FOR(i, 0, T-1){
        b.push_back(Y[i]);
    }
    return solve(p, q, a, b);
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccR6B2na.o: in function `main':
grader.cpp:(.text.startup+0x3d5): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x468): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status