oj.uz

Submission #1100456

# Submission time Handle Problem Language Result Execution time Memory
1100456 2024-10-14T02:44:33 Z Nurislam Factories (JOI14_factories) C++17
100 / 100
 7599 ms 248084 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}
 
template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}
typedef long long ll;
const ll n = 5e5+5, inf = 1e17;
vector<vector<array<int,2>>> g(n);

vector<vector<int> > lc(22, vector<int> (n, 0));
vector<ll> ds(n, 0), tin(n),tout(n);
int tim = 0;
void dfs(int ps, int pr){
	lc[0][ps] = pr;
	for (int i = 1; i < 22; i++)
	{
		lc[i][ps] = lc[i-1][lc[i-1][ps]];
	}
	tin[ps] = tim++;
	for(auto [to, d]:g[ps]){
		if(to == pr)continue;
		ds[to] = ds[ps] + d;
		dfs(to, ps);
	}
	tout[ps] = tim++;
}
int lca (int a, int b){
	if(tin[a] < tin[b] && tout[b] < tout[a])return a;
	if(tin[b] < tin[a] && tout[a] < tout[b])return b;
	for(int i = 20; i >= 0; i--){
		int na = lc[i][a];
		if(tin[na] < tin[b] && tout[b] < tout[na])continue;
		a = na;
	}
	return lc[0][a];
}
ll get(int a,int b){
	if(a == b)return 0;
	int l = lca(a, b);
	return ds[a] + ds[b] - 2*ds[l];
}
vector<int> vs(n, 0);
vector<int> have;
vector<int> sub(n, 0);
vector<vector<int>> par(n);
vector<ll> res(n,inf);
int ns;
void clacS(int v, int pr){
	sub[v] = 1;
	have.pb(v);
	for(auto [to, d]:g[v]){
		if(vs[to] || to == pr)continue;
		clacS(to, v);
		sub[v] += sub[to];
	}
}

int centr(int ps, int pr){
	for(auto [to, d]:g[ps]){
		if(vs[to] || to == pr)continue;
		if(sub[to] > ns/2)return centr(to, ps);
	}
	return ps;
}


void decm(int ps){
	have.clear();
	clacS(ps, ps);
	ns = sub[ps];
	int cur = centr(ps, ps);
	for(auto v:have){
		par[v].pb(cur);
	}
	vs[cur] = 1;
	for(auto [to,d]:g[cur]){
		if(vs[to])continue;
		decm(to);
	}
}





void Init(int N, int A[], int B[], int D[]) {
	
	for(int i = 0; i < N-1; i++){
		g[A[i]].pb({B[i], D[i]});
		g[B[i]].pb({A[i], D[i]});
	}
	dfs(0,0);
	decm(0);
}
long long Query(int S, int X[], int T, int Y[]) {
	vector<int> tod;
	for(int i = 0; i < S; i++){
		//cout << X[i] << ":\n";
		for(auto v:par[X[i]]){
			//cout << v << ' ';
			chmin(res[v], get(v, X[i]));
			//cout << get(v, X[i]) << '\n';
			tod.pb(v);
		}
		//cout << '\n';
	}
	ll ans = inf;
	for(int i = 0; i < T; i++){
		for(auto v:par[Y[i]]){
			chmin(ans, res[v] + get(v, Y[i]));
		}
	}
	for(auto x:tod)res[x] = inf;
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 103076 KB Output is correct
2 Correct 477 ms 117156 KB Output is correct
3 Correct 844 ms 113572 KB Output is correct
4 Correct 824 ms 117668 KB Output is correct
5 Correct 539 ms 117644 KB Output is correct
6 Correct 205 ms 117016 KB Output is correct
7 Correct 856 ms 117156 KB Output is correct
8 Correct 897 ms 117156 KB Output is correct
9 Correct 497 ms 116900 KB Output is correct
10 Correct 200 ms 116900 KB Output is correct
11 Correct 778 ms 116332 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 103076 KB Output is correct
2 Correct 1913 ms 186308 KB Output is correct
3 Correct 4771 ms 205320 KB Output is correct
4 Correct 726 ms 165272 KB Output is correct
5 Correct 2471 ms 241260 KB Output is correct
6 Correct 4635 ms 206116 KB Output is correct
7 Correct 2883 ms 134316 KB Output is correct
8 Correct 320 ms 129472 KB Output is correct
9 Correct 1014 ms 139172 KB Output is correct
10 Correct 2613 ms 134864 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 103076 KB Output is correct
2 Correct 477 ms 117156 KB Output is correct
3 Correct 844 ms 113572 KB Output is correct
4 Correct 824 ms 117668 KB Output is correct
5 Correct 539 ms 117644 KB Output is correct
6 Correct 205 ms 117016 KB Output is correct
7 Correct 856 ms 117156 KB Output is correct
8 Correct 897 ms 117156 KB Output is correct
9 Correct 497 ms 116900 KB Output is correct
10 Correct 200 ms 116900 KB Output is correct
11 Correct 778 ms 116332 KB Output is correct
12 Correct 47 ms 103076 KB Output is correct
13 Correct 1913 ms 186308 KB Output is correct
14 Correct 4771 ms 205320 KB Output is correct
15 Correct 726 ms 165272 KB Output is correct
16 Correct 2471 ms 241260 KB Output is correct
17 Correct 4635 ms 206116 KB Output is correct
18 Correct 2883 ms 134316 KB Output is correct
19 Correct 320 ms 129472 KB Output is correct
20 Correct 1014 ms 139172 KB Output is correct
21 Correct 2613 ms 134864 KB Output is correct
22 Correct 2658 ms 194328 KB Output is correct
23 Correct 2835 ms 199380 KB Output is correct
24 Correct 7204 ms 217908 KB Output is correct
25 Correct 7414 ms 219016 KB Output is correct
26 Correct 7599 ms 210740 KB Output is correct
27 Correct 3374 ms 248084 KB Output is correct
28 Correct 860 ms 172700 KB Output is correct
29 Correct 6583 ms 210196 KB Output is correct
30 Correct 6905 ms 209704 KB Output is correct
31 Correct 7165 ms 210308 KB Output is correct
32 Correct 1036 ms 146672 KB Output is correct
33 Correct 303 ms 130360 KB Output is correct
34 Correct 894 ms 131496 KB Output is correct
35 Correct 823 ms 131892 KB Output is correct
36 Correct 2420 ms 133288 KB Output is correct
37 Correct 2536 ms 133408 KB Output is correct