Submission #142772

#	Time	Username	Problem	Language	Result	Execution time	Memory
142772		Lawliet	Factories (JOI14_factories)	C++14	100 / 100	5131 ms	206440 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"

#define LOG 20
#define MAX 500010
#define INF 1000000000000000000LL

using namespace std;
typedef long long int lli;

int N;

int sub[MAX];
int paiCentroid[MAX];
int profCentroid[MAX];

lli minDist[MAX];
lli distCentroid[MAX][LOG];

bool isCentroid[MAX];

vector<int> peso[MAX];
vector<int> grafo[MAX];

void DFSInit(int i, int p)
{
	sub[ i ] = 1;

	for(int g = 0 ; g < grafo[i].size() ; g++)
	{
		int prox = grafo[i][g];

		if(prox == p) continue;
		if(isCentroid[ prox ]) continue;

		DFSInit(prox , i);

		sub[ i ] += sub[ prox ];
	}
}

int findCentroid(int i, int p, int s)
{
	for(int g = 0 ; g < grafo[i].size() ; g++)
	{
		int prox = grafo[i][g];

		if(prox == p) continue;
		if(isCentroid[ prox ]) continue;

		if(sub[prox] > s/2) return findCentroid(prox , i , s);
	}

	return i;
}

void DFSCalculate(int i, int p, int l)
{
	for(int g = 0 ; g < grafo[i].size() ; g++)
	{
		int prox = grafo[i][g];
		int w = peso[i][g];

		if(prox == p) continue;
		if(isCentroid[ prox ]) continue;

		distCentroid[prox][l] = distCentroid[i][l] + w;

		DFSCalculate(prox , i , l);
	}
}

void decompose(int i, int p)
{
	DFSInit(i , 0);

	int curCentroid = findCentroid(i , 0 , sub[i]);

	minDist[ curCentroid ] = INF;
	paiCentroid[ curCentroid ] = p;
	isCentroid[ curCentroid ] = true;
	profCentroid[ curCentroid ] = profCentroid[ p ] + 1;

	DFSCalculate(curCentroid , 0 , profCentroid[ curCentroid ]);

	for(int g = 0 ; g < grafo[ curCentroid ].size() ; g++)
	{
		int prox = grafo[ curCentroid ][g];

		if(isCentroid[ prox ]) continue;

		decompose(prox , curCentroid);
	}
}

void Init(int n, int A[], int B[], int D[])
{
	N = n;

	for(int g = 0 ; g < N - 1 ; g++)
	{
		int i = A[ g ] + 1;
		int j = B[ g ] + 1;
		int w = D[ g ];

		grafo[ i ].push_back( j );
		grafo[ j ].push_back( i );

		peso[ i ].push_back( w );
		peso[ j ].push_back( w );
	}

	decompose(1 , 0);
}

void update(int i, bool t)
{
	int cur = i;
	int curProf = profCentroid[ i ];

	while( true )
	{
		lli curDist = distCentroid[ i ][ curProf ];

		if( !t ) minDist[ cur ] = INF; 
		else minDist[ cur ] = min( minDist[ cur ] , curDist );

		if( paiCentroid[ cur ] == 0 ) break;

		curProf--;
		cur = paiCentroid[ cur ];
	}
}

lli query(int i)
{
	int cur = i;
	lli ans = INF;

	int curProf = profCentroid[ i ];

	while( true )
	{
		lli curDist = distCentroid[ i ][ curProf ];
		ans = min(ans , minDist[ cur ] + curDist);

		if( paiCentroid[ cur ] == 0 ) break;

		curProf--;
		cur = paiCentroid[ cur ];
	}

	return ans;
}

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

	lli ans = INF;

	for(int g = 0 ; g < T ; g++)
		ans = min(ans , query( Y[ g ] + 1 ));

	for(int g = 0 ; g < S ; g++)
		update(X[ g ] + 1 , false);

	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void DFSInit(int, int)':
factories.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < grafo[i].size() ; g++)
                  ~~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'int findCentroid(int, int, int)':
factories.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < grafo[i].size() ; g++)
                  ~~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'void DFSCalculate(int, int, int)':
factories.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < grafo[i].size() ; g++)
                  ~~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'void decompose(int, int)':
factories.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < grafo[ curCentroid ].size() ; g++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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