oj.uz

Submission #780229

# Submission time Handle Problem Language Result Execution time Memory
780229 2023-07-12T07:27:22 Z daoquanglinh2007 Factories (JOI14_factories) C++17
100 / 100
 3158 ms 161180 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pil pair <int, ll>
#define fi first
#define se second
#define mp make_pair

const int NM = 5e5, LOG = 18;
const ll inf = 1e18;

int n;
vector <pil> adj[NM], son[NM];
int parent[NM], h[NM], jump[NM][LOG+1];
ll d[NM];
int t, s[NM], e[NM];
vector <int> L;
stack <int> st;
int col[NM];
ll dp1[NM], dp2[NM], res;

void DFS(int u){
	s[u] = ++t;
	for (int i = 0; i < adj[u].size(); i++){
		int v = adj[u][i].fi;
		if (h[v] != -1) continue;
		parent[v] = u;
		h[v] = h[u]+1;
		d[v] = d[u]+(ll)adj[u][i].se;
		DFS(v);
	}
	e[u] = t;
}

void build(){
	for (int i = 0; i < n; i++) jump[i][0] = parent[i];
	for (int j = 1; (1<<j) < n; j++)
		for (int i = 0; i < n; i++)
			jump[i][j] = (jump[i][j-1] == -1 ? -1 : jump[jump[i][j-1]][j-1]);
}

void Init(int N, int A[], int B[], int D[]){
	n = N;
	for (int i = 0; i < n; i++)
		adj[i].clear();
	for (int i = 0; i < n-1; i++){
		adj[A[i]].push_back(mp(B[i], (ll)D[i]));
		adj[B[i]].push_back(mp(A[i], (ll)D[i]));
	}
	parent[0] = -1; h[1] = 0; d[1] = 0;
	for (int i = 1; i < n; i++) h[i] = -1;
	t = 0;
	DFS(0);
	build();
}

bool cmp(int x, int y){
	return s[x] < s[y];
}

int LCA(int u, int v){
	if (h[u] < h[v]) swap(u, v);
	for (int i = __lg(h[u]); i >= 0; i--)
		if (h[u]-(1<<i) >= h[v]) u = jump[u][i];
	if (u == v) return u;
	for (int i = __lg(h[u]); i >= 0; i--)
		if (jump[u][i] != -1 && jump[u][i] != jump[v][i]){
			u = jump[u][i];
			v = jump[v][i];
		}
	return parent[u];
}

bool is_ancestor(int a, int u){
	return s[a] <= s[u] && e[a] >= e[u];
}

void DFS2(int u){
	dp1[u] = dp2[u] = +inf;
	for (int i = 0; i < son[u].size(); i++){
		int v = son[u][i].fi;
		ll c = son[u][i].se;
		DFS2(v);
		res = min(res, dp1[u]+dp2[v]+c);
		res = min(res, dp2[u]+dp1[v]+c);
		dp1[u] = min(dp1[u], dp1[v]+c);
		dp2[u] = min(dp2[u], dp2[v]+c);
	}
	if (col[u] == 1){
		dp1[u] = 0;
		res = min(res, dp2[u]);
	}
	else if (col[u] == 2){
		dp2[u] = 0;
		res = min(res, dp1[u]);
	}
}

ll Query(int S, int X[], int T, int Y[]){
	L.clear();
	for (int i = 0; i < S; i++){
		col[X[i]] = 1;
		L.push_back(X[i]);
	}
	for (int i = 0; i < T; i++){
		col[Y[i]] = 2;
		L.push_back(Y[i]);
	}
	sort(L.begin(), L.end(), cmp);
	for (int i = 0; i+1 < S+T; i++){
		int a = LCA(L[i], L[i+1]);
		if (col[a] == 0){
			col[a] = 3;
			L.push_back(a);
		}
	}
	sort(L.begin(), L.end(), cmp);
	for (int i = 0; i < (int)L.size(); i++)
		son[L[i]].clear();
	while (!st.empty()) st.pop();
	st.push(L[0]);
	for (int i = 1; i < (int)L.size(); i++){
		while (!is_ancestor(st.top(), L[i])) st.pop();
		son[st.top()].push_back(mp(L[i], d[L[i]]-d[st.top()]));
		st.push(L[i]);
	}
	res = +inf;
	DFS2(L[0]);
	for (int i = 0; i < (int)L.size(); i++)
		col[L[i]] = 0;
	return res;
}

Compilation message

factories.cpp: In function 'void DFS(int)':
factories.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for (int i = 0; i < adj[u].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'void DFS2(int)':
factories.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for (int i = 0; i < son[u].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24148 KB Output is correct
2 Correct 614 ms 32832 KB Output is correct
3 Correct 673 ms 32864 KB Output is correct
4 Correct 636 ms 33000 KB Output is correct
5 Correct 550 ms 33204 KB Output is correct
6 Correct 471 ms 32808 KB Output is correct
7 Correct 699 ms 32808 KB Output is correct
8 Correct 651 ms 32980 KB Output is correct
9 Correct 559 ms 33128 KB Output is correct
10 Correct 488 ms 32804 KB Output is correct
11 Correct 697 ms 32900 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24020 KB Output is correct
2 Correct 1169 ms 121228 KB Output is correct
3 Correct 1863 ms 125524 KB Output is correct
4 Correct 754 ms 118580 KB Output is correct
5 Correct 1820 ms 159932 KB Output is correct
6 Correct 1949 ms 126820 KB Output is correct
7 Correct 1469 ms 52472 KB Output is correct
8 Correct 557 ms 51784 KB Output is correct
9 Correct 1147 ms 58684 KB Output is correct
10 Correct 1345 ms 53580 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24148 KB Output is correct
2 Correct 614 ms 32832 KB Output is correct
3 Correct 673 ms 32864 KB Output is correct
4 Correct 636 ms 33000 KB Output is correct
5 Correct 550 ms 33204 KB Output is correct
6 Correct 471 ms 32808 KB Output is correct
7 Correct 699 ms 32808 KB Output is correct
8 Correct 651 ms 32980 KB Output is correct
9 Correct 559 ms 33128 KB Output is correct
10 Correct 488 ms 32804 KB Output is correct
11 Correct 697 ms 32900 KB Output is correct
12 Correct 14 ms 24020 KB Output is correct
13 Correct 1169 ms 121228 KB Output is correct
14 Correct 1863 ms 125524 KB Output is correct
15 Correct 754 ms 118580 KB Output is correct
16 Correct 1820 ms 159932 KB Output is correct
17 Correct 1949 ms 126820 KB Output is correct
18 Correct 1469 ms 52472 KB Output is correct
19 Correct 557 ms 51784 KB Output is correct
20 Correct 1147 ms 58684 KB Output is correct
21 Correct 1345 ms 53580 KB Output is correct
22 Correct 2295 ms 131428 KB Output is correct
23 Correct 2161 ms 132220 KB Output is correct
24 Correct 2816 ms 135804 KB Output is correct
25 Correct 2849 ms 138828 KB Output is correct
26 Correct 3158 ms 129460 KB Output is correct
27 Correct 2787 ms 161180 KB Output is correct
28 Correct 1560 ms 126404 KB Output is correct
29 Correct 3118 ms 128104 KB Output is correct
30 Correct 3145 ms 127576 KB Output is correct
31 Correct 3107 ms 128072 KB Output is correct
32 Correct 1342 ms 60436 KB Output is correct
33 Correct 789 ms 55788 KB Output is correct
34 Correct 1254 ms 51500 KB Output is correct
35 Correct 1128 ms 51284 KB Output is correct
36 Correct 1195 ms 52176 KB Output is correct
37 Correct 1239 ms 52156 KB Output is correct