oj.uz

Submission #890373

# Submission time Handle Problem Language Result Execution time Memory
890373 2023-12-21T05:11:04 Z pan Factories (JOI14_factories) C++17
33 / 100
 8000 ms 235444 KB 
#ifndef FACTORIES_H_
#define FACTORIES_H_
#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
ll const MAXN = 500005;
ll sub[MAXN], lvl[MAXN], par[MAXN], m[MAXN], dist[MAXN];
vector<pi> V[MAXN];
ll twok[MAXN][25];
ll depth[MAXN];
ll n;
// 2k decomposition
void dfs(ll p, ll node)
{
	for (pi u: V[node])
	{
		if (p==u.f) continue;
		dist[u.f] = dist[node] + u.s;
		twok[u.f][0] = node;
		depth[u.f] = depth[node]+1;
		dfs(node, u.f);
	}
	
}
ll kpar(ll x, ll k)
{
	for (ll i=0; i<20; ++i)
	{
		if (k& (1<<i)) 
		{
			x=twok[x][i];
		}
	}
	return x;
}



ll lca(ll a, ll b)
{
	if (depth[a]<depth[b]) swap(a,b);
	a = kpar(a, depth[a]-depth[b]);
	if (a==b) return a;
	for (ll k=19; k>=0; k--)
	{
		if (twok[a][k]!=twok[b][k])
		{
			a=twok[a][k]; b = twok[b][k];
		}
	}
	return twok[a][0];
	
}

ll sp(ll a, ll b)
{
	return dist[a]+dist[b]-2*dist[lca(a,b)];
}

// centroid decomposition
ll dfs1(int u, int p, int l) {
	sub[u] = 1; // Subtree size is 1
	for (pi v : V[u]) {
		if (lvl[v.f] != -1) continue; // Already added to centroid tree
		if (v.f == p) continue;
		sub[u] += dfs1(v.f, u, l); // Increase size of subtree
	}
	return sub[u];
}
ll dfs2(int u, int p, int n) { // Pass in the size of the subtree
	for (pi v : V[u]) {
		if (lvl[v.f] != -1) continue; // Already added to centroid tree
		if (v.f != p && sub[v.f] > n / 2) {
			return dfs2(v.f, u, n); // DFS to that node
		}
	}
	return u; // No child has size more than n/2, hence you are the centroid
}
// Building from node u, with a parent p and level l
void build(int u, int p, int l) {
	int n = dfs1(u, p, l); // Find the size of each subtree
	int cent = dfs2(u, p, n); // Find the centroid
	if (p == -1) p = cent; // Parent of root is yourself
	par[cent] = p; // Set the parent of centroid to the previous centroid
	lvl[cent] = l;
	for (pi v : V[cent]) {
		if (lvl[v.f] != -1) continue;
// If we have already added to centroid then we ignore
		build(v.f, cent, l + 1); // Recursively build each subtree
	}
}

//To construct the centroid tree, call build(root, -1, 0);



void Init(int N, int A[], int B[], int D[])
{
	n=N;
	for (ll i=0; i<n-1; ++i)
	{
		V[A[i]].pb(mp(B[i], D[i]));
		V[B[i]].pb(mp(A[i], D[i]));
	}
	dist[0]=0;
	depth[0] = 0;
	twok[0][0] = -1;
	dfs(-1,0);
	for (ll k=1; k<20; k++)
	{
		for (ll x=0; x<n; ++x)
		{
			if (twok[x][k-1]==-1) continue;
			twok[x][k] = twok[twok[x][k-1]][k-1];
		}
	}
	memset(lvl, -1, sizeof lvl);
	build(0, -1, 0);
	for (ll i=0; i<=n-1; ++i) {m[i]=LLONG_MAX;} // < n not <n-1
}


long long Query(int S, int X[], int T, int Y[])
{
	for (ll i=0; i<S; ++i)
	{
		ll nxt = X[i];
		m[nxt] = 0;
		while (par[nxt]!=nxt)
		{
			nxt = par[nxt];
			m[nxt] = min(m[nxt], sp(nxt, X[i]));
			//cout << "sp is " << sp(nxt, X[i]) << endl;
			//cout << "nxt become " << m[nxt] << endl;
		}
		
	}
	ll ans  = LLONG_MAX;
	for (ll i=0; i<T; ++i)
	{
		//cout << i << endl;
		ll nxt = Y[i];
		//cout << " nxt is " << nxt << endl;
		ans = min(ans, m[nxt]); // dont declare ans again
		//cout << "ans become " << ans << endl;
		while (par[nxt]!=nxt)
		{
			nxt = par[nxt];
			//cout << " go to " << nxt << endl;
			if (m[nxt]!=LLONG_MAX) {ans = min(ans, m[nxt] + sp(nxt, Y[i]));}
			//cout << "sp is " << sp(nxt, Y[i]) << endl;
			//cout << "ans become " << ans << endl;
		}
	}
	for (ll i=0; i<S; ++i)
	{
		ll nxt = X[i];
		m[nxt] = LLONG_MAX;
		while (par[nxt]!=nxt) {nxt = par[nxt]; m[nxt]=LLONG_MAX;}
	}
	//cout << "final ans is " << endl;
	return ans;
}

#endif  /* FACTORIES_H_ */

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 49756 KB Output is correct
2 Correct 609 ms 61648 KB Output is correct
3 Correct 1249 ms 61528 KB Output is correct
4 Correct 988 ms 61500 KB Output is correct
5 Correct 1296 ms 61784 KB Output is correct
6 Correct 186 ms 61384 KB Output is correct
7 Correct 1310 ms 61516 KB Output is correct
8 Correct 1363 ms 61512 KB Output is correct
9 Correct 1332 ms 61788 KB Output is correct
10 Correct 184 ms 61532 KB Output is correct
11 Correct 1327 ms 61524 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 47704 KB Output is correct
2 Correct 2276 ms 196872 KB Output is correct
3 Correct 4059 ms 205344 KB Output is correct
4 Correct 583 ms 198432 KB Output is correct
5 Correct 6101 ms 235444 KB Output is correct
6 Correct 4496 ms 206244 KB Output is correct
7 Correct 2524 ms 94964 KB Output is correct
8 Correct 310 ms 93888 KB Output is correct
9 Correct 2606 ms 98784 KB Output is correct
10 Correct 2426 ms 95776 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 49756 KB Output is correct
2 Correct 609 ms 61648 KB Output is correct
3 Correct 1249 ms 61528 KB Output is correct
4 Correct 988 ms 61500 KB Output is correct
5 Correct 1296 ms 61784 KB Output is correct
6 Correct 186 ms 61384 KB Output is correct
7 Correct 1310 ms 61516 KB Output is correct
8 Correct 1363 ms 61512 KB Output is correct
9 Correct 1332 ms 61788 KB Output is correct
10 Correct 184 ms 61532 KB Output is correct
11 Correct 1327 ms 61524 KB Output is correct
12 Correct 16 ms 47704 KB Output is correct
13 Correct 2276 ms 196872 KB Output is correct
14 Correct 4059 ms 205344 KB Output is correct
15 Correct 583 ms 198432 KB Output is correct
16 Correct 6101 ms 235444 KB Output is correct
17 Correct 4496 ms 206244 KB Output is correct
18 Correct 2524 ms 94964 KB Output is correct
19 Correct 310 ms 93888 KB Output is correct
20 Correct 2606 ms 98784 KB Output is correct
21 Correct 2426 ms 95776 KB Output is correct
22 Correct 3107 ms 205964 KB Output is correct
23 Correct 2847 ms 207088 KB Output is correct
24 Execution timed out 8100 ms 210144 KB Time limit exceeded
25 Halted 0 ms 0 KB -