oj.uz

Submission #960133

# Submission time Handle Problem Language Result Execution time Memory
960133 2024-04-09T17:55:21 Z aykhn Factories (JOI14_factories) C++17
0 / 100
 2672 ms 205672 KB 
#include <bits/stdc++.h>
#include "factories.h"
 
using namespace std;
 
#define inf 0x3F3F3F3F3F3F3F3F
 
const int MXN = 5e5 + 5;
const int LOG = 21;
 
int n;
vector<array<long long, 2>> adj[MXN];
int clo[LOG][MXN], sz[MXN], used[MXN];
long long dclo[LOG][MXN], dcent[MXN];

void getsize(int a, int p)
{
	sz[a] = 1;
	for (array<long long, 2> &v : adj[a])
	{
		if (used[v[0]] || v[0] == p) continue;
		getsize(v[0], a);
		sz[a] += sz[v[0]];
	}
}

int findcent(int a, int p, int &curn)
{
	for (array<long long, 2> &v : adj[a])
	{
		if (used[v[0]] || v[0] == p) continue;
		if (sz[v[0]] * 2 > curn) return findcent(v[0], a, curn);
	}
	return a;
}

void dfs(int a, int p, int w, int &cc, int &lev)
{
	clo[lev][a] = cc;
	dclo[lev][a] = w;
	for (array<long long, 2> &v : adj[a])
	{
		if (used[v[0]] || v[0] == p) continue;
		dfs(v[0], a, w + v[1], cc, lev);
	}
}

void maincent(int a, int lev)
{
	getsize(a, a);
	int c = findcent(a, a, sz[a]);
	dfs(c, c, 0, c, lev);
	used[c] = 1;
	for (array<long long, 2> &v : adj[c])
	{
		if (used[v[0]]) continue;
		maincent(v[0], lev + 1);
	}
}
 
void Init(int N, int A[], int B[], int D[]) 
{
	n = N;
	for (int i = 0; i < n; i++)
	{
		adj[i].clear();
		sz[i] = 0;
		dcent[i] = -1;
		for (int j = 0; j < LOG; j++) clo[j][i] = -1;
	}
	for (int i = 0; i < n - 1; i++)
	{
		adj[A[i]].push_back({B[i], D[i]});
		adj[B[i]].push_back({A[i], D[i]});
	}
	maincent(0, 0);
}

 
long long Query(int S, int X[], int T, int Y[]) 
{
	long long res = inf;
	for (int i = 0; i < S; i++)
	{
		int x = X[i];
		for (int j = 0; j < LOG; j++)
		{
			if (clo[j][x] == -1) continue;
			if (dcent[clo[j][x]] == -1) dcent[clo[j][x]] = dclo[j][x];
			else dcent[clo[j][x]] = min(dcent[clo[j][x]], dclo[j][x]);
		}
	}
	for (int i = 0; i < T; i++)
	{
		int y = Y[i];
		for (int j = 0; j < LOG; j++)
		{
			if (clo[j][y] == -1 || dcent[clo[j][y]] == -1) continue;
			res = min(res, dclo[j][y] + dcent[clo[j][y]]);
		}
	}
	for (int i = 0; i < S; i++)
	{
		int x = X[i];
		for (int j = 0; j < LOG; j++)
		{
			if (clo[j][x] == -1) continue;
			dcent[clo[j][x]] = -1;
		}
	}
	return res;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 39944 KB Output is correct
2 Correct 262 ms 52052 KB Output is correct
3 Incorrect 275 ms 52304 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 41816 KB Output is correct
2 Correct 1684 ms 185608 KB Output is correct
3 Incorrect 2672 ms 205672 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 39944 KB Output is correct
2 Correct 262 ms 52052 KB Output is correct
3 Incorrect 275 ms 52304 KB Output isn't correct
4 Halted 0 ms 0 KB -