oj.uz

Submission #798771

# Submission time Handle Problem Language Result Execution time Memory
798771 2023-07-31T03:55:41 Z OrazB Factories (JOI14_factories) C++14
33 / 100
 8000 ms 129328 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second

const int N = 5e5+5;
const ll inf = 1e18;
int rem[N], sub[N], par[N], sp[N][20], lvl[N];
ll w[N], cur[N];
vector<pii> E[N];

void dfs(int nd, int pr){
	sub[nd] = 1;
	for (auto i : E[nd]){
		if (i.ff == pr or rem[i.ff]) continue;
		dfs(i.ff, nd);
		sub[nd] += sub[i.ff];
	}
}
int centroid(int nd, int pr, int sz){
	for (auto i : E[nd]){
		if (i.ff == pr or rem[i.ff]) continue;
		if (sub[i.ff]*2 > sz) return centroid(i.ff, nd, sz);
	}
	return nd;
}
void build(int nd, int pr){
	int centr = centroid(nd, 0, sub[nd]);
	rem[centr] = 1;
	par[centr] = pr;
	for (auto i : E[centr]){
		if (!rem[i.ff]){
			dfs(i.ff, 0);
			build(i.ff, centr);
		}
	}
}
void dfs2(int nd, int pr){
	sp[nd][0] = pr;
	for (auto i : E[nd]){
		if (i.ff == pr) continue;
		lvl[i.ff] = lvl[nd]+1;
		w[i.ff] = w[nd]+i.ss;
		dfs2(i.ff, nd);
	}
}
int LCA(int u, int v){
	if (lvl[u] < lvl[v]) swap(u, v);
	int diff = lvl[u]-lvl[v];
	for (int i = 19; i >= 0; i--){
		if (diff&(1<<i)) u = sp[u][i];
	}
	if (u == v) return v;
	for (int i = 19; i >= 0; i--){
		if (sp[u][i] != sp[v][i]){
			u = sp[u][i];
			v = sp[v][i];
		}
	}
	return sp[u][0];
}
ll dist(int u, int v){
	if (u == v) return 0ll;
	return w[u]+w[v]-2*w[LCA(u,v)];
}
void Init(int n, int A[], int B[], int D[]){
	for (int i = 0; i < n-1; i++){
		A[i]++;
		B[i]++;
		E[A[i]].pb({B[i], D[i]});
		E[B[i]].pb({A[i], D[i]});
	}
	dfs(1, 0);
	build(1, 0);
	dfs2(1, 0);
	for (int j = 1; j <= 19; j++){
		for (int i = 1; i <= n; i++) sp[i][j] = sp[sp[i][j-1]][j-1];
	}
	for (int i = 1; i <= n; i++) cur[i] = inf;
}
void remv(int nd){
	while(nd){
		cur[nd] = inf;
		nd = par[nd];
	}
}
void paint(int nd){
	int u = nd;
	while(u){
		cur[u] = min(cur[u], dist(u, nd));
		u = par[u];
	}
}
ll find(int nd){
	ll mn = inf;
	int u = nd;
	while(u){
		mn = min(mn, dist(u, nd)+cur[u]);
		u = par[u];
	}
	return mn;
}
ll Query(int S, int X[], int T, int Y[]){
	for (int i = 0; i < S; i++){
		X[i]++;
		paint(X[i]);
	}
	ll ans = inf;
	for (int i = 0; i < T; i++){
		Y[i]++;
		ans = min(ans, find(Y[i]));
	}
	for (int i = 0; i < S; i++) remv(X[i]);
	return ans;
}


// int main ()
// {
// 	int n, q;
// 	cin >> n >> q;
// 	int A[n], B[n], D[n];
// 	for (int i = 0; i < n-1; i++){
// 		cin >> A[i] >> B[i] >> D[i];
// 	}
// 	Init(n, A, B, D);
// 	for (int i = 0; i < q; i++){
// 		int S, T;
// 		cin >> S >> T;
// 		int X[S], Y[T];
// 		for (int j = 0; j < S; j++) cin >> X[j];
// 		for (int j = 0; j < T; j++) cin >> Y[j];
// 		cout << Query(S, X, T, Y) << '\n';
// 	}
// }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12628 KB Output is correct
2 Correct 494 ms 22000 KB Output is correct
3 Correct 1062 ms 21672 KB Output is correct
4 Correct 1047 ms 21748 KB Output is correct
5 Correct 1208 ms 21960 KB Output is correct
6 Correct 193 ms 21608 KB Output is correct
7 Correct 1077 ms 21628 KB Output is correct
8 Correct 1102 ms 21760 KB Output is correct
9 Correct 1201 ms 21964 KB Output is correct
10 Correct 179 ms 21664 KB Output is correct
11 Correct 1063 ms 21640 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12316 KB Output is correct
2 Correct 1876 ms 98836 KB Output is correct
3 Correct 4461 ms 101340 KB Output is correct
4 Correct 604 ms 99668 KB Output is correct
5 Correct 7564 ms 129328 KB Output is correct
6 Correct 4841 ms 102324 KB Output is correct
7 Correct 2752 ms 38480 KB Output is correct
8 Correct 303 ms 39032 KB Output is correct
9 Correct 3029 ms 42676 KB Output is correct
10 Correct 2799 ms 39680 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12628 KB Output is correct
2 Correct 494 ms 22000 KB Output is correct
3 Correct 1062 ms 21672 KB Output is correct
4 Correct 1047 ms 21748 KB Output is correct
5 Correct 1208 ms 21960 KB Output is correct
6 Correct 193 ms 21608 KB Output is correct
7 Correct 1077 ms 21628 KB Output is correct
8 Correct 1102 ms 21760 KB Output is correct
9 Correct 1201 ms 21964 KB Output is correct
10 Correct 179 ms 21664 KB Output is correct
11 Correct 1063 ms 21640 KB Output is correct
12 Correct 7 ms 12316 KB Output is correct
13 Correct 1876 ms 98836 KB Output is correct
14 Correct 4461 ms 101340 KB Output is correct
15 Correct 604 ms 99668 KB Output is correct
16 Correct 7564 ms 129328 KB Output is correct
17 Correct 4841 ms 102324 KB Output is correct
18 Correct 2752 ms 38480 KB Output is correct
19 Correct 303 ms 39032 KB Output is correct
20 Correct 3029 ms 42676 KB Output is correct
21 Correct 2799 ms 39680 KB Output is correct
22 Correct 2818 ms 100344 KB Output is correct
23 Correct 2893 ms 102480 KB Output is correct
24 Execution timed out 8042 ms 102744 KB Time limit exceeded
25 Halted 0 ms 0 KB -