oj.uz

Submission #798763

# Submission time Handle Problem Language Result Execution time Memory
798763 2023-07-31T03:44:09 Z OrazB Factories (JOI14_factories) C++14
33 / 100
 8000 ms 158684 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, ll>
#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 16 ms 12628 KB Output is correct
2 Correct 495 ms 27068 KB Output is correct
3 Correct 1103 ms 30412 KB Output is correct
4 Correct 1072 ms 30420 KB Output is correct
5 Correct 1214 ms 30728 KB Output is correct
6 Correct 183 ms 30368 KB Output is correct
7 Correct 1082 ms 30404 KB Output is correct
8 Correct 1175 ms 30580 KB Output is correct
9 Correct 1216 ms 30748 KB Output is correct
10 Correct 182 ms 30412 KB Output is correct
11 Correct 1126 ms 30440 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 1905 ms 105836 KB Output is correct
3 Correct 4481 ms 109684 KB Output is correct
4 Correct 619 ms 103664 KB Output is correct
5 Correct 7430 ms 140300 KB Output is correct
6 Correct 4807 ms 110324 KB Output is correct
7 Correct 2688 ms 39544 KB Output is correct
8 Correct 286 ms 39224 KB Output is correct
9 Correct 2936 ms 44100 KB Output is correct
10 Correct 2810 ms 40768 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12628 KB Output is correct
2 Correct 495 ms 27068 KB Output is correct
3 Correct 1103 ms 30412 KB Output is correct
4 Correct 1072 ms 30420 KB Output is correct
5 Correct 1214 ms 30728 KB Output is correct
6 Correct 183 ms 30368 KB Output is correct
7 Correct 1082 ms 30404 KB Output is correct
8 Correct 1175 ms 30580 KB Output is correct
9 Correct 1216 ms 30748 KB Output is correct
10 Correct 182 ms 30412 KB Output is correct
11 Correct 1126 ms 30440 KB Output is correct
12 Correct 8 ms 12244 KB Output is correct
13 Correct 1905 ms 105836 KB Output is correct
14 Correct 4481 ms 109684 KB Output is correct
15 Correct 619 ms 103664 KB Output is correct
16 Correct 7430 ms 140300 KB Output is correct
17 Correct 4807 ms 110324 KB Output is correct
18 Correct 2688 ms 39544 KB Output is correct
19 Correct 286 ms 39224 KB Output is correct
20 Correct 2936 ms 44100 KB Output is correct
21 Correct 2810 ms 40768 KB Output is correct
22 Correct 2900 ms 131128 KB Output is correct
23 Correct 2846 ms 133752 KB Output is correct
24 Correct 7818 ms 135068 KB Output is correct
25 Correct 7546 ms 138932 KB Output is correct
26 Correct 7677 ms 135288 KB Output is correct
27 Execution timed out 8052 ms 158684 KB Time limit exceeded
28 Halted 0 ms 0 KB -