oj.uz

Submission #798777

# Submission time Handle Problem Language Result Execution time Memory
798777 2023-07-31T04:04:12 Z OrazB Factories (JOI14_factories) C++17
33 / 100
 8000 ms 129204 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 15 ms 12444 KB Output is correct
2 Correct 500 ms 20896 KB Output is correct
3 Correct 1101 ms 20960 KB Output is correct
4 Correct 1075 ms 20836 KB Output is correct
5 Correct 1220 ms 21124 KB Output is correct
6 Correct 185 ms 20836 KB Output is correct
7 Correct 1080 ms 20860 KB Output is correct
8 Correct 1116 ms 20868 KB Output is correct
9 Correct 1213 ms 21124 KB Output is correct
10 Correct 181 ms 20896 KB Output is correct
11 Correct 1059 ms 20868 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 1900 ms 98308 KB Output is correct
3 Correct 4561 ms 100784 KB Output is correct
4 Correct 626 ms 98964 KB Output is correct
5 Correct 7739 ms 129204 KB Output is correct
6 Correct 4962 ms 102016 KB Output is correct
7 Correct 2786 ms 37848 KB Output is correct
8 Correct 294 ms 38400 KB Output is correct
9 Correct 3028 ms 42036 KB Output is correct
10 Correct 2959 ms 39020 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12444 KB Output is correct
2 Correct 500 ms 20896 KB Output is correct
3 Correct 1101 ms 20960 KB Output is correct
4 Correct 1075 ms 20836 KB Output is correct
5 Correct 1220 ms 21124 KB Output is correct
6 Correct 185 ms 20836 KB Output is correct
7 Correct 1080 ms 20860 KB Output is correct
8 Correct 1116 ms 20868 KB Output is correct
9 Correct 1213 ms 21124 KB Output is correct
10 Correct 181 ms 20896 KB Output is correct
11 Correct 1059 ms 20868 KB Output is correct
12 Correct 7 ms 12244 KB Output is correct
13 Correct 1900 ms 98308 KB Output is correct
14 Correct 4561 ms 100784 KB Output is correct
15 Correct 626 ms 98964 KB Output is correct
16 Correct 7739 ms 129204 KB Output is correct
17 Correct 4962 ms 102016 KB Output is correct
18 Correct 2786 ms 37848 KB Output is correct
19 Correct 294 ms 38400 KB Output is correct
20 Correct 3028 ms 42036 KB Output is correct
21 Correct 2959 ms 39020 KB Output is correct
22 Correct 2855 ms 99900 KB Output is correct
23 Correct 2865 ms 102136 KB Output is correct
24 Execution timed out 8061 ms 102560 KB Time limit exceeded
25 Halted 0 ms 0 KB -