oj.uz

Submission #798782

# Submission time Handle Problem Language Result Execution time Memory
798782 2023-07-31T04:13:30 Z OrazB Factories (JOI14_factories) C++14
33 / 100
 8000 ms 129164 KB 
#include <iostream>
#include <vector>
#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 19 ms 12408 KB Output is correct
2 Correct 519 ms 20820 KB Output is correct
3 Correct 1075 ms 20872 KB Output is correct
4 Correct 1095 ms 20860 KB Output is correct
5 Correct 1222 ms 21128 KB Output is correct
6 Correct 181 ms 20872 KB Output is correct
7 Correct 1097 ms 20872 KB Output is correct
8 Correct 1100 ms 20868 KB Output is correct
9 Correct 1218 ms 21252 KB Output is correct
10 Correct 184 ms 20860 KB Output is correct
11 Correct 1070 ms 20956 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 1939 ms 98204 KB Output is correct
3 Correct 4711 ms 100812 KB Output is correct
4 Correct 632 ms 99012 KB Output is correct
5 Correct 7417 ms 129164 KB Output is correct
6 Correct 5029 ms 102200 KB Output is correct
7 Correct 2806 ms 39276 KB Output is correct
8 Correct 314 ms 39936 KB Output is correct
9 Correct 3229 ms 43416 KB Output is correct
10 Correct 2967 ms 40624 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12408 KB Output is correct
2 Correct 519 ms 20820 KB Output is correct
3 Correct 1075 ms 20872 KB Output is correct
4 Correct 1095 ms 20860 KB Output is correct
5 Correct 1222 ms 21128 KB Output is correct
6 Correct 181 ms 20872 KB Output is correct
7 Correct 1097 ms 20872 KB Output is correct
8 Correct 1100 ms 20868 KB Output is correct
9 Correct 1218 ms 21252 KB Output is correct
10 Correct 184 ms 20860 KB Output is correct
11 Correct 1070 ms 20956 KB Output is correct
12 Correct 7 ms 12244 KB Output is correct
13 Correct 1939 ms 98204 KB Output is correct
14 Correct 4711 ms 100812 KB Output is correct
15 Correct 632 ms 99012 KB Output is correct
16 Correct 7417 ms 129164 KB Output is correct
17 Correct 5029 ms 102200 KB Output is correct
18 Correct 2806 ms 39276 KB Output is correct
19 Correct 314 ms 39936 KB Output is correct
20 Correct 3229 ms 43416 KB Output is correct
21 Correct 2967 ms 40624 KB Output is correct
22 Correct 2984 ms 100400 KB Output is correct
23 Correct 3006 ms 102780 KB Output is correct
24 Execution timed out 8061 ms 103004 KB Time limit exceeded
25 Halted 0 ms 0 KB -