oj.uz

Submission #222942

# Submission time Handle Problem Language Result Execution time Memory
222942 2020-04-14T11:43:28 Z arnold518 Factories (JOI14_factories) C++14
100 / 100
 6225 ms 205960 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e5;
const ll INF = 1e18;

int N;
vector<pii> adj[MAXN+10];

int sz[MAXN+10], del[MAXN+10], cenpar[MAXN+10], cendep[MAXN+10];
ll dist[MAXN+10][30];

void getsz(int now, int bef)
{
	sz[now]=1;
	for(auto &nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		getsz(nxt.first, now);
		sz[now]+=sz[nxt.first];
	}
}

int getcen(int now, int bef, int S)
{
	for(auto &nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		if(sz[nxt.first]>S/2) return getcen(nxt.first, now, S);
	}
	return now;
}

void dfs(int now, int bef, ll d, int cdep)
{
	dist[now][cdep]=d;
	for(auto &nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		dfs(nxt.first, now, d+nxt.second, cdep);
	}
}

void decomp(int now, int cdep, int bef)
{
	getsz(now, now);
	now=getcen(now, now, sz[now]);
	cendep[now]=cdep;
	cenpar[now]=bef;
		
	dfs(now, now, 0, cdep);
	del[now]=true;

	for(auto &nxt : adj[now])
	{
		if(del[nxt.first]) continue;
		decomp(nxt.first, cdep+1, now);
	}
}

ll A[MAXN+10], B[MAXN+10];

void Init(int _N, int AA[], int BB[], int D[])
{
	int i, j;
	N=_N;
	for(i=0; i<N-1; i++)
	{
		int u=AA[i]+1, v=BB[i]+1, w=D[i];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	decomp(1, 1, 0);
	for(i=1; i<=N; i++) A[i]=B[i]=INF;
}

ll Query(int S, int X[], int T, int Y[])
{
	int i, j;

	vector<int> V;
	for(i=0; i<S; i++)
	{
		int now=X[i]+1, u=X[i]+1;
		while(now)
		{
			A[now]=min(A[now], dist[u][cendep[now]]);
			V.push_back(now);
			now=cenpar[now];
		}
	}

	for(i=0; i<T; i++)
	{
		int now=Y[i]+1, u=Y[i]+1;
		while(now)
		{
			B[now]=min(B[now], dist[u][cendep[now]]);
			V.push_back(now);
			now=cenpar[now];
		}
	}

	ll ans=INF;
	for(auto it : V) ans=min(ans, A[it]+B[it]);
	for(auto it : V) A[it]=B[it]=INF;
	return ans;
}

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:73:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:87:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12800 KB Output is correct
2 Correct 497 ms 24544 KB Output is correct
3 Correct 585 ms 24464 KB Output is correct
4 Correct 577 ms 25044 KB Output is correct
5 Correct 608 ms 25276 KB Output is correct
6 Correct 374 ms 28140 KB Output is correct
7 Correct 559 ms 28024 KB Output is correct
8 Correct 578 ms 28624 KB Output is correct
9 Correct 616 ms 28580 KB Output is correct
10 Correct 359 ms 28024 KB Output is correct
11 Correct 571 ms 28024 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12416 KB Output is correct
2 Correct 2622 ms 176972 KB Output is correct
3 Correct 3895 ms 177604 KB Output is correct
4 Correct 1065 ms 177616 KB Output is correct
5 Correct 5195 ms 194480 KB Output is correct
6 Correct 4116 ms 179092 KB Output is correct
7 Correct 1364 ms 61144 KB Output is correct
8 Correct 699 ms 61800 KB Output is correct
9 Correct 1583 ms 64660 KB Output is correct
10 Correct 1428 ms 62496 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12800 KB Output is correct
2 Correct 497 ms 24544 KB Output is correct
3 Correct 585 ms 24464 KB Output is correct
4 Correct 577 ms 25044 KB Output is correct
5 Correct 608 ms 25276 KB Output is correct
6 Correct 374 ms 28140 KB Output is correct
7 Correct 559 ms 28024 KB Output is correct
8 Correct 578 ms 28624 KB Output is correct
9 Correct 616 ms 28580 KB Output is correct
10 Correct 359 ms 28024 KB Output is correct
11 Correct 571 ms 28024 KB Output is correct
12 Correct 14 ms 12416 KB Output is correct
13 Correct 2622 ms 176972 KB Output is correct
14 Correct 3895 ms 177604 KB Output is correct
15 Correct 1065 ms 177616 KB Output is correct
16 Correct 5195 ms 194480 KB Output is correct
17 Correct 4116 ms 179092 KB Output is correct
18 Correct 1364 ms 61144 KB Output is correct
19 Correct 699 ms 61800 KB Output is correct
20 Correct 1583 ms 64660 KB Output is correct
21 Correct 1428 ms 62496 KB Output is correct
22 Correct 3093 ms 190620 KB Output is correct
23 Correct 3314 ms 192908 KB Output is correct
24 Correct 4749 ms 198348 KB Output is correct
25 Correct 4985 ms 200996 KB Output is correct
26 Correct 4894 ms 180372 KB Output is correct
27 Correct 6225 ms 205960 KB Output is correct
28 Correct 1322 ms 189824 KB Output is correct
29 Correct 4744 ms 179884 KB Output is correct
30 Correct 4812 ms 179600 KB Output is correct
31 Correct 4794 ms 179916 KB Output is correct
32 Correct 1615 ms 76232 KB Output is correct
33 Correct 662 ms 63172 KB Output is correct
34 Correct 987 ms 59404 KB Output is correct
35 Correct 1008 ms 59428 KB Output is correct
36 Correct 1338 ms 60044 KB Output is correct
37 Correct 1250 ms 59808 KB Output is correct