oj.uz

Submission #798781

# Submission time Handle Problem Language Result Execution time Memory
798781 2023-07-31T04:10:01 Z OrazB Factories (JOI14_factories) C++14
15 / 100
 8000 ms 127808 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 23 ms 12520 KB Output is correct
2 Correct 758 ms 24780 KB Output is correct
3 Correct 1295 ms 23988 KB Output is correct
4 Correct 1351 ms 23932 KB Output is correct
5 Correct 1345 ms 24228 KB Output is correct
6 Correct 233 ms 23932 KB Output is correct
7 Correct 1252 ms 24004 KB Output is correct
8 Correct 1281 ms 23972 KB Output is correct
9 Correct 1384 ms 24232 KB Output is correct
10 Correct 219 ms 23480 KB Output is correct
11 Correct 1308 ms 22268 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12244 KB Output is correct
2 Correct 2431 ms 98276 KB Output is correct
3 Correct 5597 ms 100688 KB Output is correct
4 Correct 620 ms 99044 KB Output is correct
5 Execution timed out 8090 ms 127808 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 12520 KB Output is correct
2 Correct 758 ms 24780 KB Output is correct
3 Correct 1295 ms 23988 KB Output is correct
4 Correct 1351 ms 23932 KB Output is correct
5 Correct 1345 ms 24228 KB Output is correct
6 Correct 233 ms 23932 KB Output is correct
7 Correct 1252 ms 24004 KB Output is correct
8 Correct 1281 ms 23972 KB Output is correct
9 Correct 1384 ms 24232 KB Output is correct
10 Correct 219 ms 23480 KB Output is correct
11 Correct 1308 ms 22268 KB Output is correct
12 Correct 7 ms 12244 KB Output is correct
13 Correct 2431 ms 98276 KB Output is correct
14 Correct 5597 ms 100688 KB Output is correct
15 Correct 620 ms 99044 KB Output is correct
16 Execution timed out 8090 ms 127808 KB Time limit exceeded
17 Halted 0 ms 0 KB -