oj.uz

Submission #798780

# Submission time Handle Problem Language Result Execution time Memory
798780 2023-07-31T04:08:43 Z OrazB Factories (JOI14_factories) C++11
15 / 100
 8000 ms 128628 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 12444 KB Output is correct
2 Correct 666 ms 20832 KB Output is correct
3 Correct 1314 ms 20852 KB Output is correct
4 Correct 1383 ms 20848 KB Output is correct
5 Correct 1385 ms 21136 KB Output is correct
6 Correct 220 ms 20872 KB Output is correct
7 Correct 1203 ms 20840 KB Output is correct
8 Correct 1308 ms 20884 KB Output is correct
9 Correct 1415 ms 21144 KB Output is correct
10 Correct 241 ms 21680 KB Output is correct
11 Correct 1238 ms 22780 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12244 KB Output is correct
2 Correct 2765 ms 99004 KB Output is correct
3 Correct 6529 ms 101568 KB Output is correct
4 Correct 861 ms 99832 KB Output is correct
5 Execution timed out 8032 ms 128628 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 12444 KB Output is correct
2 Correct 666 ms 20832 KB Output is correct
3 Correct 1314 ms 20852 KB Output is correct
4 Correct 1383 ms 20848 KB Output is correct
5 Correct 1385 ms 21136 KB Output is correct
6 Correct 220 ms 20872 KB Output is correct
7 Correct 1203 ms 20840 KB Output is correct
8 Correct 1308 ms 20884 KB Output is correct
9 Correct 1415 ms 21144 KB Output is correct
10 Correct 241 ms 21680 KB Output is correct
11 Correct 1238 ms 22780 KB Output is correct
12 Correct 10 ms 12244 KB Output is correct
13 Correct 2765 ms 99004 KB Output is correct
14 Correct 6529 ms 101568 KB Output is correct
15 Correct 861 ms 99832 KB Output is correct
16 Execution timed out 8032 ms 128628 KB Time limit exceeded
17 Halted 0 ms 0 KB -