oj.uz

Submission #903849

# Submission time Handle Problem Language Result Execution time Memory
903849 2024-01-11T12:24:58 Z KN200711 Factories (JOI14_factories) C++14
100 / 100
 7425 ms 173604 KB 
#include "factories.h"
# include <bits/stdc++.h>
# define ll long long
# define ld long double
# define fi first
# define se second
# define pll pair<ll, ll>
# define pdd pair<ld, ld>
# define pii pair<int, int>
using namespace std;

vector<pii> edge[500001];
int in[500001], ot[500001], par[500001], sp[20][500001], dpt[500001], t, N1;
ll dist[500001], seg[2][2000001];

void dfs(int a, int pr, ll dis) {
	dist[a] = dis;
	in[a] = ++t;
	par[a] = pr;
	for(auto p : edge[a]) {
		if(p.fi == pr) continue;
		dpt[p.fi] = dpt[a] + 1;
		dfs(p.fi, a, dis + 1ll * p.se);
	}
	ot[a] = t;
}

void build_sp() {
	for(int i=0;i<20;i++) {
		for(int k=0;k<N1;k++) {
			if(i == 0) sp[i][k] = par[k];
			else sp[i][k] = sp[i - 1][sp[i - 1][k]];
		}
	}
}

int LCA(int a, int b) {
	if(dpt[a] < dpt[b]) swap(a, b);
	int sel = dpt[a] - dpt[b];
	for(int k=19;k>=0;k--) {
		if(sel&(1 << k)) {
			a = sp[k][a];
		}
	}
	if(a == b) return a;
	for(int k=19;k>=0;k--) {
		if(sp[k][a] != sp[k][b]) {
			a = sp[k][a];
			b = sp[k][b];
		}
	}
	return par[a];
}

void build(int lf, int rg, int nd) {
	seg[0][nd] = seg[1][nd] = 1e18;
	if(lf != rg) {
		int mid = (lf + rg) / 2;
		build(lf, mid, 2*nd + 1);
		build(mid+1, rg, 2*nd+2);
	}
}

void upd(int lf, int rg, int nd, int pos, int ty, ll val) {
	if(lf == rg) seg[ty][nd] = val;
	else {
		int mid = (lf + rg) / 2;
		if(pos <= mid) upd(lf, mid, 2*nd+1, pos, ty, val);
		else upd(mid+1, rg, 2*nd+2, pos, ty, val);
		seg[ty][nd] = min(seg[ty][2*nd+1], seg[ty][2*nd+2]);
	}
}

ll qry(int lf, int rg, int nd, int clf, int crg, int ty) {
	if(lf > crg || clf > rg) return 1e18;
	if(clf <= lf && rg <= crg) return seg[ty][nd];
	int mid = (lf + rg) / 2;
	return min(qry(lf, mid, 2*nd+1, clf, crg, ty), qry(mid+1, rg, 2*nd+2, clf, crg, ty));
}

void Init(int N, int A[], int B[], int D[]) {
	t = -1;
	N1 = N;
	for(int i=0;i<N-1;i++) {
		edge[A[i]].push_back(make_pair(B[i], D[i]));
		edge[B[i]].push_back(make_pair(A[i], D[i]));
	}
	dfs(0, -1, 0);
	build_sp();
//	cout<<"build sp"<<endl;
	build(0, N-1, 0);
//	cout<<"build"<<endl;
}

ll ans;

void cek(int a) {
//	cout<<"a : "<<a<<" "<<qry(0, N1-1, 0, in[a], ot[a], 0)<<" "<<qry(0, N1-1, 0, in[a], ot[a], 1)<<" "<<dist[a]<<endl;
	ll d = qry(0, N1-1, 0, in[a], ot[a], 0) + qry(0, N1-1, 0, in[a], ot[a], 1) - 2ll * dist[a];
	ans = min(ans, d);
}

long long Query(int S, int X[], int T, int Y[]) {
	vector<pii> arr;
	arr.clear();
	for(int i=0;i<S;i++) {
		upd(0, N1 - 1, 0, in[X[i]], 0, dist[X[i]]);
		arr.push_back({in[X[i]], X[i]});
	}
	for(int i=0;i<T;i++) {
		upd(0, N1-1, 0, in[Y[i]], 1, dist[Y[i]]);
		arr.push_back({in[Y[i]], Y[i]});
	}
	sort(arr.begin(), arr.end());
	ans = 1e18;
	for(int i=0;i<arr.size();i++) {
		cek(arr[i].se);
		if(i + 1 < arr.size()) {
			cek(LCA(arr[i].se, arr[i + 1].se));
		}
	}
	for(int i=0;i<S;i++) {
		upd(0, N1 - 1, 0, in[X[i]], 0, 1e18);
	}
	for(int i=0;i<T;i++) {
		upd(0, N1-1, 0, in[Y[i]], 1, 1e18);
	}
	return ans;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:116:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |  for(int i=0;i<arr.size();i++) {
      |              ~^~~~~~~~~~~
factories.cpp:118:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |   if(i + 1 < arr.size()) {
      |      ~~~~~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 82728 KB Output is correct
2 Correct 1701 ms 94392 KB Output is correct
3 Correct 1996 ms 94380 KB Output is correct
4 Correct 1804 ms 94460 KB Output is correct
5 Correct 1734 ms 94760 KB Output is correct
6 Correct 1425 ms 94568 KB Output is correct
7 Correct 1924 ms 94424 KB Output is correct
8 Correct 1828 ms 94480 KB Output is correct
9 Correct 1725 ms 94708 KB Output is correct
10 Correct 1567 ms 94408 KB Output is correct
11 Correct 1949 ms 94420 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 80472 KB Output is correct
2 Correct 2856 ms 142772 KB Output is correct
3 Correct 3772 ms 145284 KB Output is correct
4 Correct 2242 ms 142992 KB Output is correct
5 Correct 3095 ms 173604 KB Output is correct
6 Correct 4113 ms 146304 KB Output is correct
7 Correct 3885 ms 107672 KB Output is correct
8 Correct 2912 ms 107484 KB Output is correct
9 Correct 2866 ms 111100 KB Output is correct
10 Correct 3871 ms 108268 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 82728 KB Output is correct
2 Correct 1701 ms 94392 KB Output is correct
3 Correct 1996 ms 94380 KB Output is correct
4 Correct 1804 ms 94460 KB Output is correct
5 Correct 1734 ms 94760 KB Output is correct
6 Correct 1425 ms 94568 KB Output is correct
7 Correct 1924 ms 94424 KB Output is correct
8 Correct 1828 ms 94480 KB Output is correct
9 Correct 1725 ms 94708 KB Output is correct
10 Correct 1567 ms 94408 KB Output is correct
11 Correct 1949 ms 94420 KB Output is correct
12 Correct 13 ms 80472 KB Output is correct
13 Correct 2856 ms 142772 KB Output is correct
14 Correct 3772 ms 145284 KB Output is correct
15 Correct 2242 ms 142992 KB Output is correct
16 Correct 3095 ms 173604 KB Output is correct
17 Correct 4113 ms 146304 KB Output is correct
18 Correct 3885 ms 107672 KB Output is correct
19 Correct 2912 ms 107484 KB Output is correct
20 Correct 2866 ms 111100 KB Output is correct
21 Correct 3871 ms 108268 KB Output is correct
22 Correct 4944 ms 149172 KB Output is correct
23 Correct 5148 ms 149428 KB Output is correct
24 Correct 5250 ms 151812 KB Output is correct
25 Correct 5547 ms 153248 KB Output is correct
26 Correct 7172 ms 150732 KB Output is correct
27 Correct 4720 ms 173256 KB Output is correct
28 Correct 4289 ms 150984 KB Output is correct
29 Correct 7170 ms 150260 KB Output is correct
30 Correct 7409 ms 149624 KB Output is correct
31 Correct 7425 ms 150336 KB Output is correct
32 Correct 2832 ms 112684 KB Output is correct
33 Correct 2852 ms 108568 KB Output is correct
34 Correct 3785 ms 106196 KB Output is correct
35 Correct 3779 ms 106048 KB Output is correct
36 Correct 4142 ms 106792 KB Output is correct
37 Correct 4040 ms 106764 KB Output is correct