Submission #709519

#	Time	Username	Problem	Language	Result	Execution time	Memory
709519		Ahmed57	Factories (JOI14_factories)	C++14	Compilation error	0 ms	0 KiB

factories

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>

using namespace std;
vector<pair<int,long long>> adj[200001];
int hi[200001];
int P[200001][18];
long long sum[200001][18];
void dfs(int i,int pr,long long len){
    hi[i] = hi[pr]+1;
    P[i][0]= pr;
    sum[i][0] =len;
    for(int j = 1;j<18;j++){
        P[i][j] = P[P[i][j-1]][j-1];
        sum[i][j]= sum[i][j-1]+sum[P[i][j-1]][j-1];
    }
    for(auto j:adj[i]){
        if(j.first!=pr){
            dfs(j.first,i,j.second);
        }
    }
}long long lca(int x,int y){
    long long su = 0;
    if(hi[x]<hi[y]) swap(x,y);
    for(int k=17;k>=0;k--)
    {
        if(hi[x]-(1<<k) >= hi[y]){
            su+=sum[x][k];
            x=P[x][k];
        }
    }
    if(x==y) return su;
    for(int k=17;k>=0;k--)
    {
        if(P[x][k] != P[y][k]){
            su+=sum[x][k]+sum[y][k];
            x=P[x][k],y=P[y][k];
        }
    }
    return su+sum[x][0]+sum[y][0];
}
int sz[200001];
int vis[200001];
int par[200001];
long long best[200001];
int vi[200001];
int va = 1;
void upd(int i){
    long long s = i;
    while(s!=-1){
        if(vi[s]!=va){
            vi[s] =va;
            best[s] = 1e18;
        }
        best[s] = min(best[s],lca(i,s));
        s= par[s];
    }
}
long long ans(int i){
    long long s = i , re = 1e18;
    while(s!=-1){
        if(vi[s]!=va){
            vi[s] =va;
            best[s] = 1e18;
        }
        re = min(re,best[s]+lca(i,s));
        s= par[s];
    }
    return re;
}
int find_size(int v, int p = -1) {
    if(vis[v]) return 0;
    sz[v] = 1;
    for(auto x: adj[v]) {
        if (x.first != p) {
            sz[v] += find_size(x.first, v);
        }
    }
    return sz[v];
}
int find_centroid(int v, int p, int n) {
    for (auto x: adj[v]) {
        if (x.first != p) {
            if (!vis[x.first] && sz[x.first] > n / 2) {
                return find_centroid(x.first, v, n);
            }
        }
    }
    return v;
}
void centroid(int v = 0, int p = -1) {
    find_size(v);
    int c = find_centroid(v,-1,sz[v]);
    vis[c] = true;
    par[c] = p;
    for(auto x:adj[c]) {
        if (!vis[x.first]) {
            centroid(x.first, c);
        }
    }
}
void init(int N,int A[],int B[],int D[]){
    for(int i = 0;i<N-1;i++){
        adj[A[i]].push_back({B[i],D[i]});
        adj[B[i]].push_back({A[i],D[i]});
    }
    centroid();
    dfs(0,0,0);
}
long long Query(int S, int X[], int T,int Y[]) {
	for(int i = 0;i<S;i++){
        upd(X[i]);
	}
	long long Res = 1e18;
	for(int i = 0;i<T;i++){
        Res = min(Res,ans(Y[i]));
	}
	va++;
	return Res;
}

Compilation message (stderr)

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