Submission #310668

#	Time	Username	Problem	Language	Result	Execution time	Memory
310668		vipghn2003	Factories (JOI14_factories)	C++14	15 / 100	8016 ms	114784 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,int A[],int B[],int D[])
{
    n=N;
    for(int i=1;i<=n;i++) mn[i]=1e18;
    m=n-1;
    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,int X[],int T,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;
}

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