oj.uz

Submission #798773

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

const int N = 5e5+2;
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;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12500 KB Output is correct
2 Correct 492 ms 21404 KB Output is correct
3 Correct 1072 ms 21368 KB Output is correct
4 Correct 1033 ms 21384 KB Output is correct
5 Correct 1220 ms 21644 KB Output is correct
6 Correct 182 ms 21352 KB Output is correct
7 Correct 1076 ms 21336 KB Output is correct
8 Correct 1117 ms 21396 KB Output is correct
9 Correct 1200 ms 21616 KB Output is correct
10 Correct 181 ms 21324 KB Output is correct
11 Correct 1062 ms 21420 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12244 KB Output is correct
2 Correct 1888 ms 98564 KB Output is correct
3 Correct 4464 ms 100952 KB Output is correct
4 Correct 620 ms 99516 KB Output is correct
5 Correct 7528 ms 129380 KB Output is correct
6 Correct 4824 ms 102132 KB Output is correct
7 Correct 2849 ms 38128 KB Output is correct
8 Correct 293 ms 38624 KB Output is correct
9 Correct 2971 ms 42196 KB Output is correct
10 Correct 2760 ms 39340 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12500 KB Output is correct
2 Correct 492 ms 21404 KB Output is correct
3 Correct 1072 ms 21368 KB Output is correct
4 Correct 1033 ms 21384 KB Output is correct
5 Correct 1220 ms 21644 KB Output is correct
6 Correct 182 ms 21352 KB Output is correct
7 Correct 1076 ms 21336 KB Output is correct
8 Correct 1117 ms 21396 KB Output is correct
9 Correct 1200 ms 21616 KB Output is correct
10 Correct 181 ms 21324 KB Output is correct
11 Correct 1062 ms 21420 KB Output is correct
12 Correct 7 ms 12244 KB Output is correct
13 Correct 1888 ms 98564 KB Output is correct
14 Correct 4464 ms 100952 KB Output is correct
15 Correct 620 ms 99516 KB Output is correct
16 Correct 7528 ms 129380 KB Output is correct
17 Correct 4824 ms 102132 KB Output is correct
18 Correct 2849 ms 38128 KB Output is correct
19 Correct 293 ms 38624 KB Output is correct
20 Correct 2971 ms 42196 KB Output is correct
21 Correct 2760 ms 39340 KB Output is correct
22 Correct 2724 ms 100232 KB Output is correct
23 Correct 2861 ms 102568 KB Output is correct
24 Correct 7942 ms 102668 KB Output is correct
25 Correct 7743 ms 106496 KB Output is correct
26 Execution timed out 8045 ms 103116 KB Time limit exceeded
27 Halted 0 ms 0 KB -