제출 #219735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
219735		nafis_shifat	공장들 (JOI14_factories)	C++14	15 / 100	8087 ms	275444 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;


const int mxn=5e5+6;
const ll inf=1e18;
vector<int> tree[mxn];
vector<ll> cost[mxn];

int subsz[mxn]={};
int centroidMarked[mxn]={};
int cpar[mxn];
ll cdist[30][mxn];

int level[mxn];
int dp[20][mxn];
ll dist[20][mxn];

int n;



ll ans[mxn];


void dfs1(int cur,int prev,ll cst)
{
	level[cur]=(cur==0?1 :level[prev]+1);
 
	dp[0][cur]=prev;
	dist[0][cur]=cst;
 
	for(int i=1;i<20;i++)
	{
		dp[i][cur]=dp[i-1][dp[i-1][cur]];
		dist[i][cur]=dist[i-1][cur]+dist[i-1][dp[i-1][cur]];
	}
 
 
	for(int i=0;i<tree[cur].size();i++)
	{
		int v=tree[cur][i];
		if(v==prev)continue;
		dfs1(v,cur,cost[cur][i]);
	}
}

int findLCA(int u,int v)
{
	if(level[u]<level[v])swap(u,v);
    int diff=level[u]-level[v];
    for(int i=0;i<20;i++)if((diff>>i)&1)u=dp[i][u];
    if(u==v)return u;
    for(int i=19;i>=0;i--)
    {
      if(dp[i][u]!=dp[i][v]){
        u=dp[i][u];
        v=dp[i][v];
      }
    }
 
    return dp[0][u];
}

ll getDist(int u,int v)
{
	if(u==v)return 0;
	if(level[u]<level[v])swap(u,v);
    int diff=level[u]-level[v];
    ll sum=0;
    for(int i=0;i<20;i++)
    {
    	if((diff>>i)&1)
    	{
    		sum+=dist[i][u];
    		u=dp[i][u];
    	}
    }

    return sum;

}


void dfs(int cur,int prev)
{
	subsz[cur]=1;
	for(auto i:tree[cur])
	{
		if(i!=prev && !centroidMarked[i])
		{
			dfs(i,cur);
			subsz[cur]+=subsz[i];
		}
	}

}
int getcentroid(int cur,int prev,int sz)
{
	bool isC=true;
	int hc=-1;
	for(auto i:tree[cur])
	{
		if(i!=prev && !centroidMarked[i] && subsz[i]>sz)
		{
			isC=false;
			hc=i;
			break;
		}
	}
	if(isC && subsz[cur]>=sz)return cur;
	return getcentroid(hc,cur,sz);
}


int getcentroid(int src)
{
	dfs(src,-1);
	int c=getcentroid(src,-1,subsz[src]/2);
	centroidMarked[c]=1;
	return c;
}

int build(int root)
{
	int c=getcentroid(root);
	
	for(auto i:tree[c])
	{
		if(!centroidMarked[i])
		{
			int k=build(i);
			cpar[k]=c;

			
		}
	}



	return c;
	
}


void Init(int N, int A[], int B[], int D[])
{
	n=N;
	for(int i=0;i<n-1;i++)
	{
	    //cout<<A[i]<<"    "<<B[i]<<endl;
		tree[A[i]].push_back(B[i]);
		tree[B[i]].push_back(A[i]);

		cost[A[i]].push_back(D[i]);
		cost[B[i]].push_back(D[i]);
	}

	dfs1(0,-1,0);
	
	cpar[build(0)]=-1;
    for(int i=0;i<n;i++)ans[i]=inf;
	for(int i=0;i<n;i++)
	{

		int x=1;
		int cur=i;
		while(cur!=-1)
		{
			int lca=findLCA(i,cur);
			cdist[x++][i]=getDist(i,lca)+getDist(lca,cur);
			cur=cpar[cur];
		}
	}
    
}


void prc(int u,bool f)
{
	
	int x=2;
	ans[u]=(f?0:inf);
	int cur=cpar[u];
	while(cur!=-1)
	{
		if(f)ans[cur]=min(ans[cur],cdist[x++][u]);
		else ans[cur]=inf;
		
		cur=cpar[cur];
	}
}

long long Query(int S, int X[], int T, int Y[])
{
	for(int i=0;i<S;i++)prc(X[i],true);

	ll res=inf;

    for(int i=0;i<T;i++)
    {
    	int x=1;
    	int cur=Y[i];

    	while(cur!=-1)
    	{
    		res=min(res,ans[cur]+cdist[x++][Y[i]]);
    		cur=cpar[cur];
    	}
    }

    for(int i=0;i<S;i++)prc(X[i],false);



    return res;
}

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

factories.cpp: In function 'void dfs1(int, int, long long int)':
factories.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tree[cur].size();i++)
              ~^~~~~~~~~~~~~~~~~

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