Submission #219737

#	Time	Username	Problem	Language	Result	Execution time	Memory
219737		nafis_shifat	Factories (JOI14_factories)	C++14	0 / 100	27 ms	24192 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[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,ll cst)
{
	bool isC=true;
	int hc=-1;
	ll w;
	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;
			w=cost[cur][i];
			break;
		}
	}
	if(isC && subsz[cur]>=sz)
	{
		finW=cst;
		return cur;
	}
	return getcentroid(hc,cur,sz,cst+w);
}


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

int build(int root)
{
	int c=getcentroid(root);
	
	for(int i=0;i<tree[c].size();i++)
	{
		int v=tree[c][i];
		if(!centroidMarked[v])
		{
			int k=build(v);
			cpar[k]=c;

			cdist[k]= finW+cost[c][i];
		}
	}

	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;

}


void prc(int u,bool f)
{
	
	int x=2;
	ans[u]=(f?0:inf);
	int cur=cpar[u];

	ll s=cdist[u];
	while(cur!=-1)
	{
		if(f)ans[cur]=min(ans[cur],s);
		else ans[cur]=inf;
		s+=cdist[cur];
		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];
    	ll s=0;
    	while(cur!=-1)
    	{
    		res=min(res,ans[cur]+s);
    		s+=cdist[cur];
    		cur=cpar[cur];

    	}
    }

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



    return res;
}

Compilation message (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, long long 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 'int build(int)':
factories.cpp:93:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tree[c].size();i++)
              ~^~~~~~~~~~~~~~~
factories.cpp: In function 'void prc(int, bool)':
factories.cpp:134:6: warning: unused variable 'x' [-Wunused-variable]
  int x=2;
      ^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:157:10: warning: unused variable 'x' [-Wunused-variable]
      int x=1;
          ^
factories.cpp: In function 'int getcentroid(int, int, int, long long int)':
factories.cpp:77:20: warning: 'w' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return getcentroid(hc,cur,sz,cst+w);
         ~~~~~~~~~~~^~~~~~~~~~~~~~~~~

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