oj.uz

Submission #780181

# Submission time Handle Problem Language Result Execution time Memory
780181 2023-07-12T07:09:13 Z vjudge1 Factories (JOI14_factories) C++17
100 / 100
 4488 ms 160152 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 = 5e5, LOG = 18;
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 32 ms 26196 KB Output is correct
2 Correct 693 ms 34912 KB Output is correct
3 Correct 829 ms 34804 KB Output is correct
4 Correct 752 ms 34864 KB Output is correct
5 Correct 574 ms 35076 KB Output is correct
6 Correct 540 ms 34780 KB Output is correct
7 Correct 865 ms 34800 KB Output is correct
8 Correct 829 ms 34880 KB Output is correct
9 Correct 588 ms 35072 KB Output is correct
10 Correct 529 ms 34780 KB Output is correct
11 Correct 861 ms 34800 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 26004 KB Output is correct
2 Correct 1392 ms 121952 KB Output is correct
3 Correct 2229 ms 125480 KB Output is correct
4 Correct 936 ms 122544 KB Output is correct
5 Correct 1933 ms 158648 KB Output is correct
6 Correct 2285 ms 126672 KB Output is correct
7 Correct 1692 ms 54068 KB Output is correct
8 Correct 655 ms 54008 KB Output is correct
9 Correct 1297 ms 60124 KB Output is correct
10 Correct 1675 ms 55192 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 26196 KB Output is correct
2 Correct 693 ms 34912 KB Output is correct
3 Correct 829 ms 34804 KB Output is correct
4 Correct 752 ms 34864 KB Output is correct
5 Correct 574 ms 35076 KB Output is correct
6 Correct 540 ms 34780 KB Output is correct
7 Correct 865 ms 34800 KB Output is correct
8 Correct 829 ms 34880 KB Output is correct
9 Correct 588 ms 35072 KB Output is correct
10 Correct 529 ms 34780 KB Output is correct
11 Correct 861 ms 34800 KB Output is correct
12 Correct 19 ms 26004 KB Output is correct
13 Correct 1392 ms 121952 KB Output is correct
14 Correct 2229 ms 125480 KB Output is correct
15 Correct 936 ms 122544 KB Output is correct
16 Correct 1933 ms 158648 KB Output is correct
17 Correct 2285 ms 126672 KB Output is correct
18 Correct 1692 ms 54068 KB Output is correct
19 Correct 655 ms 54008 KB Output is correct
20 Correct 1297 ms 60124 KB Output is correct
21 Correct 1675 ms 55192 KB Output is correct
22 Correct 2771 ms 132672 KB Output is correct
23 Correct 2517 ms 133412 KB Output is correct
24 Correct 3299 ms 136716 KB Output is correct
25 Correct 3546 ms 139500 KB Output is correct
26 Correct 3969 ms 129872 KB Output is correct
27 Correct 3260 ms 160152 KB Output is correct
28 Correct 1773 ms 130924 KB Output is correct
29 Correct 4067 ms 128332 KB Output is correct
30 Correct 4387 ms 127696 KB Output is correct
31 Correct 4488 ms 128260 KB Output is correct
32 Correct 1425 ms 62096 KB Output is correct
33 Correct 917 ms 57452 KB Output is correct
34 Correct 1305 ms 53268 KB Output is correct
35 Correct 1408 ms 53060 KB Output is correct
36 Correct 1884 ms 53900 KB Output is correct
37 Correct 1727 ms 53760 KB Output is correct