oj.uz

Submission #780176

# Submission time Handle Problem Language Result Execution time Memory
780176 2023-07-12T07:07:44 Z daoquanglinh2007 Factories (JOI14_factories) C++17
100 / 100
 4734 ms 189548 KB 
#include <bits/stdc++.h>
using namespace std;
 
#include "factories.h"
 
#define ll long long
#define pii pair <int, int>
#define pil pair <int, ll>
#define fi first
#define se second
#define mp make_pair
 
const int NM = 1e6, LOG = 20;
const ll inf = 1e18;
 
int N, Q;
vector <pii> adj[NM+5];
int parent[NM+5], h[NM+5], jump[NM+5][LOG+5];
ll d[NM+5];
int t, s[NM+5], e[NM+5];
vector <int> L, L1;
int col[NM+5];
stack <int> st;
vector <pil> son[NM+5];
ll dp1[NM+5], dp2[NM+5], ans;
 
void DFS(int u){
	s[u] = ++t;
	for (int i = 0; i < (int)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; j <= LOG; j++)
		for (int i = 0; i < N; i++)
			if (jump[i][j-1] != -1) jump[i][j] = jump[jump[i][j-1]][j-1];	
			else jump[i][j] = -1;
}
 
bool is_ancestor(int a, int u){
	return s[a] <= s[u] && e[a] >= e[u];
}
 
int LCA(int u, int v){
	if (h[u] < h[v]) swap(u, v);
	for (int i = LOG; i >= 0; i--)
		if (h[u]-(1<<i) >= h[v]) u = jump[u][i];
	if (u == v) return u;
	for (int i = LOG; 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];
}
 
ll dist(int u, int v){
	return d[u]+d[v]-2*d[LCA(u, v)];
}
 
bool cmp(int x, int y){
	return s[x] < s[y];
}
 
void DFS2(int u){
	dp1[u] = +inf, dp2[u] = +inf;
	for (int i = 0; i < (int)son[u].size(); i++){
		int v = son[u][i].fi;
		DFS2(v);
		ans = min(ans, dp1[u]+dp2[v]+son[u][i].se);
		ans = min(ans, dp2[u]+dp1[v]+son[u][i].se);
		dp1[u] = min(dp1[u], dp1[v]+son[u][i].se);
		dp2[u] = min(dp2[u], dp2[v]+son[u][i].se);
	}
	if (col[u] == 1){
		dp1[u] = 0;
		ans = min(ans, dp2[u]);
	}
	if (col[u] == 2){
		dp2[u] = 0;
		ans = min(ans, dp1[u]);
	}
}
 
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], D[i]));
		adj[B[i]].push_back(mp(A[i], D[i]));
	}
	parent[0] = -1, h[0] = 0, d[0] = 0;
	for (int i = 1; i < N; i++) h[i] = -1;
	t = 0;
	DFS(0);
	build();
	memset(col, 0, sizeof(col));
}
 
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);
	L1.clear();
	for (int i = 0; i < (int)L.size(); i++){
		L1.push_back(L[i]);
		if (i+1 < (int)L.size()){
			int tmp = LCA(L[i], L[i+1]);
			if (col[tmp] == 0){
				col[tmp] = 3;
				L1.push_back(tmp);
			}
		}
	}
/*	if (col[0] == 0){
		col[0] = 3;
		L1.push_back(0);
	}*/
	sort(L1.begin(), L1.end(), cmp);
	for (int i = 0; i < (int)L1.size(); i++) son[L1[i]].clear();
	while (!st.empty()) st.pop();
	for (int i = 0; i < L1.size(); i++){
		while (!st.empty() && !is_ancestor(st.top(), L1[i])) st.pop();
		if (st.empty()){
			st.push(L1[i]);
		}
		else{
			son[st.top()].push_back(mp(L1[i], dist(st.top(), L1[i])));
			st.push(L1[i]);
		}
	}
	ans = +inf;
	DFS2(L1[0]);
	for (int i = 0; i < (int)L1.size(); i++) col[L1[i]] = 0;
	return ans;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 51604 KB Output is correct
2 Correct 725 ms 60312 KB Output is correct
3 Correct 850 ms 60248 KB Output is correct
4 Correct 751 ms 60320 KB Output is correct
5 Correct 606 ms 60676 KB Output is correct
6 Correct 522 ms 60292 KB Output is correct
7 Correct 851 ms 60264 KB Output is correct
8 Correct 745 ms 60312 KB Output is correct
9 Correct 585 ms 60628 KB Output is correct
10 Correct 596 ms 60260 KB Output is correct
11 Correct 858 ms 60280 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 51412 KB Output is correct
2 Correct 1450 ms 151500 KB Output is correct
3 Correct 2380 ms 154716 KB Output is correct
4 Correct 951 ms 151860 KB Output is correct
5 Correct 2004 ms 188020 KB Output is correct
6 Correct 2468 ms 156144 KB Output is correct
7 Correct 1988 ms 80528 KB Output is correct
8 Correct 708 ms 80296 KB Output is correct
9 Correct 1419 ms 86260 KB Output is correct
10 Correct 1729 ms 81508 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 51604 KB Output is correct
2 Correct 725 ms 60312 KB Output is correct
3 Correct 850 ms 60248 KB Output is correct
4 Correct 751 ms 60320 KB Output is correct
5 Correct 606 ms 60676 KB Output is correct
6 Correct 522 ms 60292 KB Output is correct
7 Correct 851 ms 60264 KB Output is correct
8 Correct 745 ms 60312 KB Output is correct
9 Correct 585 ms 60628 KB Output is correct
10 Correct 596 ms 60260 KB Output is correct
11 Correct 858 ms 60280 KB Output is correct
12 Correct 27 ms 51412 KB Output is correct
13 Correct 1450 ms 151500 KB Output is correct
14 Correct 2380 ms 154716 KB Output is correct
15 Correct 951 ms 151860 KB Output is correct
16 Correct 2004 ms 188020 KB Output is correct
17 Correct 2468 ms 156144 KB Output is correct
18 Correct 1988 ms 80528 KB Output is correct
19 Correct 708 ms 80296 KB Output is correct
20 Correct 1419 ms 86260 KB Output is correct
21 Correct 1729 ms 81508 KB Output is correct
22 Correct 2832 ms 161928 KB Output is correct
23 Correct 2612 ms 162784 KB Output is correct
24 Correct 3411 ms 165924 KB Output is correct
25 Correct 3486 ms 169040 KB Output is correct
26 Correct 4161 ms 159272 KB Output is correct
27 Correct 3241 ms 189548 KB Output is correct
28 Correct 1690 ms 160328 KB Output is correct
29 Correct 4141 ms 157748 KB Output is correct
30 Correct 4238 ms 157104 KB Output is correct
31 Correct 4734 ms 157592 KB Output is correct
32 Correct 1267 ms 88372 KB Output is correct
33 Correct 946 ms 83584 KB Output is correct
34 Correct 1275 ms 79460 KB Output is correct
35 Correct 1280 ms 79284 KB Output is correct
36 Correct 1794 ms 80068 KB Output is correct
37 Correct 1807 ms 79988 KB Output is correct