제출 #219747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
219747		nafis_shifat	공장들 (JOI14_factories)	C++14	100 / 100	6142 ms	204024 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[24][mxn];

int level[mxn];


int n;



ll ans[mxn];

ll finW;


void dfs1(int cur,int prev,ll cst)
{
 
	for(int i=0;i<tree[cur].size();i++)
	{
		int v=tree[cur][i];
		if(v==prev)continue;
		dfs1(v,cur,cost[cur][i]);
	}
}



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(int i=0;i<tree[cur].size();i++)
	{
		int v=tree[cur][i];
		if(v!=prev && !centroidMarked[v] && subsz[v]>sz)
		{
			isC=false;
			hc=v;
			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;
}



void calc_dist(int cur,int prev,int l,ll d)
{
	cdist[l][cur]=d;
	
	for(int i=0;i<tree[cur].size();i++)
	{
		int v=tree[cur][i];
		if(v==prev || centroidMarked[v])continue;

		calc_dist(v,cur,l,d+cost[cur][i]);
	}
}


int build(int root,int lv)
{
	int c=getcentroid(root);
	calc_dist(c,-1,lv,0);
	level[c]=lv;
	for(int i=0;i<tree[c].size();i++)
	{
		int v=tree[c][i];
		if(!centroidMarked[v])
		{
			int k=build(v,lv+1);
			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++)
	{
	   
		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,0)]=-1;
    for(int i=0;i<n;i++)ans[i]=inf;

}


void prc(int u,bool f)
{
	
	int lv=level[u]-1;
	ans[u]=(f?0:inf);
	int cur=cpar[u];

	while(cur!=-1)
	{
	   
		if(f)ans[cur]=min(ans[cur],cdist[lv][u]);
		else ans[cur]=inf;
	
		cur=cpar[cur];
		lv--;
		
	}
}

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 lv=level[Y[i]]-1;
    	int cur=cpar[Y[i]];
    	res=min(res,ans[Y[i]]);
  
    	while(cur!=-1)
    	{
    	    
    		res=min(res,ans[cur]+cdist[lv][Y[i]]);
    	  
    		cur=cpar[cur];
    		lv--;

    	}
    }

    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:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tree[cur].size();i++)
              ~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'int getcentroid(int, int, int)':
factories.cpp:61:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tree[cur].size();i++)
              ~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'void calc_dist(int, int, int, long long int)':
factories.cpp:94:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tree[cur].size();i++)
              ~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'int build(int, int)':
factories.cpp:109:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tree[c].size();i++)
              ~^~~~~~~~~~~~~~~

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