oj.uz

Submission #166910

# Submission time Handle Problem Language Result Execution time Memory
166910 2019-12-04T14:19:35 Z wmrmr Factories (JOI14_factories) C++17
100 / 100
 6809 ms 202208 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const int MAX = 5e5+10, LOG = 22;
const long long int INF = 1e18;
vector<int> g[MAX], p[MAX];
vector<int> rList;
int troidProf[MAX], troidPai[MAX], sub[MAX];
long long int troidDist[LOG][MAX], mnDist[MAX];
bool isTroid[MAX], active[MAX];
void CalcSub(int v, int pai)
{
	sub[v] = 1;
	for(int i=0;i<g[v].size();i++)
	{
		int prox = g[v][i];
		if(prox == pai || isTroid[prox]) continue;
		CalcSub(prox,v);
		sub[v] += sub[prox];
	}
	return;
}
int FindTroid(int v, int pai, int sz)
{
	for(int i=0;i<g[v].size();i++)
	{
		int prox = g[v][i];
		if( prox == pai || isTroid[prox] ) continue;
		if( sub[prox] > sz/2 ) return FindTroid(prox,v,sz);
	}
	return v;
}
void CalcDist(int v, int pai, int prof)
{
	for(int i=0;i<g[v].size();i++)
	{
		int prox = g[v][i], peso = p[v][i];
		if(prox == pai || isTroid[prox]) continue;
		troidDist[prof][prox] = troidDist[prof][v] + peso;
		CalcDist(prox,v,prof);
	}
	return;
}
void Decompose(int v, int prof, int ultTroid)
{
	CalcSub(v,v);
	int troid = FindTroid(v,v,sub[v]);
	isTroid[troid] = 1;
	troidProf[troid] = prof;
	troidPai[troid] = ultTroid;
	CalcDist(troid,troid,prof);
	for(int i=0;i<g[troid].size();i++)
	{
		int prox = g[troid][i];
		if(isTroid[prox]) continue;
		Decompose(prox,prof+1,troid);
	}
	return;
}
void Init(int N, int A[], int B[], int D[])
{
	for(int i=0;i<N-1;i++)
	{
		g[ A[i] ].push_back( B[i] ); g[ B[i] ].push_back( A[i] );
		p[ A[i] ].push_back( D[i] ); p[ B[i] ].push_back( D[i] );
	}
	for(int i=0;i<N;i++) mnDist[i] = INF;
	Decompose(0,0,-1);
	return;
}
long long int Query(int S, int X[], int T, int Y[])
{
	long long int resp = INF;
	for(int i=0;i<S;i++)
	{
		int v = X[i], troid = v;
		while(troid != -1)
		{
			mnDist[troid] = min( mnDist[troid] , troidDist[ troidProf[troid] ][v] );
			rList.push_back(troid);
			troid = troidPai[troid];
		}
	}
	for(int i=0;i<T;i++)
	{
		int v = Y[i], troid = v;
		while(troid != -1)
		{
			resp = min( resp , mnDist[troid] + troidDist[ troidProf[troid] ][v] );
			troid = troidPai[troid];
		}
	}
	for(int i=0;i<rList.size();i++) mnDist[rList[i]] = INF;
	rList.clear();
	return resp;
}

Compilation message

factories.cpp: In function 'void CalcSub(int, int)':
factories.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
factories.cpp: In function 'int FindTroid(int, int, int)':
factories.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
factories.cpp: In function 'void CalcDist(int, int, int)':
factories.cpp:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
factories.cpp: In function 'void Decompose(int, int, int)':
factories.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[troid].size();i++)
              ~^~~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:93:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<rList.size();i++) mnDist[rList[i]] = INF;
              ~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 24440 KB Output is correct
2 Correct 398 ms 34056 KB Output is correct
3 Correct 439 ms 34040 KB Output is correct
4 Correct 433 ms 34336 KB Output is correct
5 Correct 470 ms 34552 KB Output is correct
6 Correct 297 ms 33604 KB Output is correct
7 Correct 445 ms 34084 KB Output is correct
8 Correct 441 ms 34136 KB Output is correct
9 Correct 478 ms 34552 KB Output is correct
10 Correct 303 ms 33732 KB Output is correct
11 Correct 441 ms 34168 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24056 KB Output is correct
2 Correct 2934 ms 135552 KB Output is correct
3 Correct 4191 ms 152060 KB Output is correct
4 Correct 975 ms 87080 KB Output is correct
5 Correct 5425 ms 176976 KB Output is correct
6 Correct 4548 ms 171124 KB Output is correct
7 Correct 1344 ms 69824 KB Output is correct
8 Correct 479 ms 59240 KB Output is correct
9 Correct 1491 ms 74916 KB Output is correct
10 Correct 1307 ms 71272 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 24440 KB Output is correct
2 Correct 398 ms 34056 KB Output is correct
3 Correct 439 ms 34040 KB Output is correct
4 Correct 433 ms 34336 KB Output is correct
5 Correct 470 ms 34552 KB Output is correct
6 Correct 297 ms 33604 KB Output is correct
7 Correct 445 ms 34084 KB Output is correct
8 Correct 441 ms 34136 KB Output is correct
9 Correct 478 ms 34552 KB Output is correct
10 Correct 303 ms 33732 KB Output is correct
11 Correct 441 ms 34168 KB Output is correct
12 Correct 26 ms 24056 KB Output is correct
13 Correct 2934 ms 135552 KB Output is correct
14 Correct 4191 ms 152060 KB Output is correct
15 Correct 975 ms 87080 KB Output is correct
16 Correct 5425 ms 176976 KB Output is correct
17 Correct 4548 ms 171124 KB Output is correct
18 Correct 1344 ms 69824 KB Output is correct
19 Correct 479 ms 59240 KB Output is correct
20 Correct 1491 ms 74916 KB Output is correct
21 Correct 1307 ms 71272 KB Output is correct
22 Correct 3489 ms 161472 KB Output is correct
23 Correct 3507 ms 167892 KB Output is correct
24 Correct 5245 ms 181316 KB Output is correct
25 Correct 5379 ms 182408 KB Output is correct
26 Correct 5368 ms 177308 KB Output is correct
27 Correct 6809 ms 202208 KB Output is correct
28 Correct 1194 ms 115468 KB Output is correct
29 Correct 5085 ms 177156 KB Output is correct
30 Correct 5155 ms 176684 KB Output is correct
31 Correct 5257 ms 177184 KB Output is correct
32 Correct 1639 ms 78008 KB Output is correct
33 Correct 514 ms 60200 KB Output is correct
34 Correct 974 ms 65400 KB Output is correct
35 Correct 1004 ms 65144 KB Output is correct
36 Correct 1393 ms 68136 KB Output is correct
37 Correct 1395 ms 68236 KB Output is correct