Submission #310665

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

factories

#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;

const int N=5e5+5;
int n,m,p[N][21],level[N],up[N],sz[N];
long long mn[N],dep[N];
bool vis[N];
vector<pii>adj[N];

void dfs(int x,int par=-1)
{
    for(int k=1;k<=20;k++) p[x][k]=p[p[x][k-1]][k-1];
    for(auto&u:adj[x])
    {
        if(u.fi==par) continue;
        p[u.fi][0]=x;
        dep[u.fi]=dep[x]+u.se;
        level[u.fi]=level[x]+1;
        dfs(u.fi,x);
    }
}

int lca(int x,int y)
{
    if(level[x]>level[y]) swap(x,y);
    int diff=level[y]-level[x];
    for(int k=20;k>=0;k--) if(diff>>k&1) y=p[y][k];
    if (x==y) return x;
    for(int k=20;k>=0;k--)
    {
        if (p[x][k]!=p[y][k])
        {
            x=p[x][k];
            y=p[y][k];
        }
    }
    return p[x][0];
}

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

void findsz(int u,int p=-1)
{
	sz[u]=1;
	for(auto&v:adj[u])
    {
		if (v.fi!=p&&!vis[v.fi])
		{
			findsz(v.fi,u);
			sz[u]+=sz[v.fi];
		}
	}
}

int find_cen(int u,int p,int m)
{
	for(auto&v:adj[u])
	{
		if(v.fi!=p&&!vis[v.fi])
        {
			if (sz[v.fi]>m/2) return find_cen(v.fi,u,m);
		}
	}
	return u;
}

void centroid(int root=1,int p=-1)
{
    findsz(root,root);
	int k=find_cen(root,root,sz[root]);
	up[k]=p;
	vis[k]=true;
	for(auto&u:adj[k]) if(!vis[u.fi])centroid(u.fi,k);
}

void init(int N,vector<int>A,vector<int>B,vector<int>D)
{
    n=N;
    for(int i=1;i<=n;i++) mn[i]=1e18;
    m=A.size();
    for(int i=0;i<m;i++)
    {
        int u=A[i];
        int v=B[i];
        u++,v++;
        int w=D[i];
        adj[u].push_back(mp(v,w));
        adj[v].push_back(mp(u,w));
    }
    dfs(1);
    centroid();
}

long long Query(int S,vector<int>X,int T,vector<int>Y)
{
    for(int i=0;i<S;i++) X[i]++;
    for(int i=0;i<T;i++)
    {
        Y[i]++;
        int cur=Y[i];
        while(cur!=-1)
        {
            mn[cur]=min(mn[cur],dist(Y[i],cur));
            cur=up[cur];
        }
    }
    long long res=1e18;
    for(int i=0;i<S;i++)
    {
        int cur=X[i];
        while(cur!=-1)
        {
            res=min(res,mn[cur]+dist(X[i],cur));
            cur=up[cur];
        }
    }
    for(int i=0;i<T;i++)
    {
        int cur=Y[i];
        while(cur!=-1)
        {
            mn[cur]=1e18;
            cur=up[cur];
        }
    }
    return res;
}
/*
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    vector<int>a(n-1),b(n-1),d(n-1);
    for(int i=0;i<n-1;i++) cin>>a[i]>>b[i]>>d[i];
    init(n,a,b,d);
    while(q--)
    {
        int s,t;
        cin>>s>>t;
        vector<int>x(s),y(t);
        for(int i=0;i<s;i++) cin>>x[i];
        for(int i=0;i<t;i++) cin>>y[i];
        cout<<Query(s,x,t,y)<<'\n';
    }
}
7 1
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
*/

Compilation message (stderr)

/tmp/ccaHZL5e.o: In function `main':
grader.cpp:(.text.startup+0x317): undefined reference to `Init(int, int*, int*, int*)'
grader.cpp:(.text.startup+0x397): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status