oj.uz

Submission #142772

# Submission time Handle Problem Language Result Execution time Memory
142772 2019-08-10T20:42:51 Z Lawliet Factories (JOI14_factories) C++14
100 / 100
 5131 ms 206440 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24440 KB Output is correct
2 Correct 382 ms 42616 KB Output is correct
3 Correct 414 ms 42696 KB Output is correct
4 Correct 405 ms 42616 KB Output is correct
5 Correct 432 ms 42828 KB Output is correct
6 Correct 310 ms 42600 KB Output is correct
7 Correct 410 ms 42744 KB Output is correct
8 Correct 409 ms 42752 KB Output is correct
9 Correct 424 ms 42916 KB Output is correct
10 Correct 310 ms 42744 KB Output is correct
11 Correct 407 ms 42560 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24184 KB Output is correct
2 Correct 2425 ms 176372 KB Output is correct
3 Correct 3634 ms 176756 KB Output is correct
4 Correct 1050 ms 178508 KB Output is correct
5 Correct 4510 ms 202340 KB Output is correct
6 Correct 3939 ms 178788 KB Output is correct
7 Correct 1127 ms 72824 KB Output is correct
8 Correct 522 ms 74064 KB Output is correct
9 Correct 1341 ms 77740 KB Output is correct
10 Correct 1141 ms 74232 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24440 KB Output is correct
2 Correct 382 ms 42616 KB Output is correct
3 Correct 414 ms 42696 KB Output is correct
4 Correct 405 ms 42616 KB Output is correct
5 Correct 432 ms 42828 KB Output is correct
6 Correct 310 ms 42600 KB Output is correct
7 Correct 410 ms 42744 KB Output is correct
8 Correct 409 ms 42752 KB Output is correct
9 Correct 424 ms 42916 KB Output is correct
10 Correct 310 ms 42744 KB Output is correct
11 Correct 407 ms 42560 KB Output is correct
12 Correct 25 ms 24184 KB Output is correct
13 Correct 2425 ms 176372 KB Output is correct
14 Correct 3634 ms 176756 KB Output is correct
15 Correct 1050 ms 178508 KB Output is correct
16 Correct 4510 ms 202340 KB Output is correct
17 Correct 3939 ms 178788 KB Output is correct
18 Correct 1127 ms 72824 KB Output is correct
19 Correct 522 ms 74064 KB Output is correct
20 Correct 1341 ms 77740 KB Output is correct
21 Correct 1141 ms 74232 KB Output is correct
22 Correct 2773 ms 183428 KB Output is correct
23 Correct 2807 ms 186232 KB Output is correct
24 Correct 4151 ms 185068 KB Output is correct
25 Correct 4385 ms 188860 KB Output is correct
26 Correct 4115 ms 185160 KB Output is correct
27 Correct 5131 ms 206440 KB Output is correct
28 Correct 1344 ms 188936 KB Output is correct
29 Correct 4416 ms 184752 KB Output is correct
30 Correct 4162 ms 184332 KB Output is correct
31 Correct 4147 ms 184812 KB Output is correct
32 Correct 1448 ms 77948 KB Output is correct
33 Correct 532 ms 74560 KB Output is correct
34 Correct 926 ms 70776 KB Output is correct
35 Correct 903 ms 70784 KB Output is correct
36 Correct 1196 ms 71268 KB Output is correct
37 Correct 1163 ms 71296 KB Output is correct