oj.uz

Submission #1086370

# Submission time Handle Problem Language Result Execution time Memory
1086370 2024-09-10T10:52:03 Z 4QT0R Factories (JOI14_factories) C++17
100 / 100
 2986 ms 232644 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long

ll oo=1e18;
vector<pair<int,ll>> graph[500003];
ll iter=0;
ll pre[500003];
ll post[500003];
ll dep[500003];
ll real_dep[500003];
ll jmp[500003][20];

int lca(int a, int b){
	if (dep[a]<dep[b])swap(a,b);
	for (int i = 19; i>=0; i--){
		if (dep[jmp[a][i]]>=dep[b])a=jmp[a][i];
	}
	if (a==b)return a;
	for (int i = 19; i>=0; i--){
		if (jmp[a][i]!=jmp[b][i]){
			a=jmp[a][i];
			b=jmp[b][i];
		}
	}
	return jmp[a][0];
}

ll dist(int a, int b){
	if (pre[a]<=pre[b] && post[a]>=post[b])return real_dep[b]-real_dep[a];
	if (pre[a]>=pre[b] && post[a]<=post[b])return real_dep[a]-real_dep[b];
	return real_dep[a]+real_dep[b]-2*real_dep[lca(a,b)];
}

void prep(int v, int p){
	pre[v]=iter++;
	jmp[v][0]=p;
	for (int i = 1; i<20; i++)jmp[v][i]=jmp[jmp[v][i-1]][i-1];
	for (auto [u,d] : graph[v]){
		if (u==p)continue;
		dep[u]=dep[v]+1;
		real_dep[u]=real_dep[v]+d;
		prep(u,v);
	}
	post[v]=iter++;
}

int n;

void Init(int N, int A[], int B[], int D[]){
	n=N;
	for (int i = 0; i<N-1; i++){
		graph[A[i]].push_back({B[i],D[i]});
		graph[B[i]].push_back({A[i],D[i]});
	}
	prep(0,0);
}

ll odl[500003];
ll fin[500003];
ll dp[500003][2];

vector<int> graph2[500003];

ll dfs(int v){
	if (fin[v])dp[v][fin[v]-1]=0;
	ll odp=oo;
	for (auto u : graph2[v]){
		if (v==u)continue;
		odp=min(odp,dfs(u));
		dp[v][0]=min(dp[v][0],dp[u][0]+real_dep[u]-real_dep[v]);
		dp[v][1]=min(dp[v][1],dp[u][1]+real_dep[u]-real_dep[v]);
	}
	graph2[v].clear();
	return min(odp,dp[v][0]+dp[v][1]);
}
ll Query(int S, int X[], int T, int Y[]){
	vector<int> tab;
	for (int i = 0; i<S; i++)tab.push_back(X[i]);
	for (int i = 0; i<T; i++)tab.push_back(Y[i]);
	for (int i = 0; i<S; i++)fin[X[i]]=1;
	for (int i = 0; i<T; i++)fin[Y[i]]=2;
	sort(tab.begin(),tab.end(), [](int a, int b){return pre[a]<pre[b];});
	int powt=tab.size();
	for (int i = 0; i<powt-1; i++){
		if ((pre[tab[i+1]]-pre[tab[i]])*(post[tab[i+1]]-post[tab[i]])>=0){
			int dod=lca(tab[i],tab[i+1]);
			if (!fin[dod])tab.push_back(dod);
		}
	}
	sort(tab.begin(),tab.end(), [](int a, int b){return pre[a]<pre[b];});
	for (auto u : tab)dp[u][0]=dp[u][1]=oo;
	ll ans=oo;
	stack<int> st;
	st.push(tab[0]);
	for (int i = 1; i<tab.size(); i++){
		while(st.size() && post[st.top()]<post[tab[i]]){
			st.pop();
		}
		graph2[st.top()].push_back(tab[i]);
		st.push(tab[i]);
	}
	ans=dfs(tab[0]);
	for (auto u : tab)dp[u][0]=dp[u][1]=0;
	for (int i = 0; i<S; i++)fin[X[i]]=0;
	for (int i = 0; i<T; i++)fin[Y[i]]=0;
	return ans;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24408 KB Output is correct
2 Correct 646 ms 42684 KB Output is correct
3 Correct 715 ms 42836 KB Output is correct
4 Correct 624 ms 42896 KB Output is correct
5 Correct 376 ms 43024 KB Output is correct
6 Correct 571 ms 42788 KB Output is correct
7 Correct 689 ms 42852 KB Output is correct
8 Correct 634 ms 42880 KB Output is correct
9 Correct 391 ms 43092 KB Output is correct
10 Correct 547 ms 42820 KB Output is correct
11 Correct 702 ms 42832 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24156 KB Output is correct
2 Correct 1184 ms 186832 KB Output is correct
3 Correct 1825 ms 189504 KB Output is correct
4 Correct 856 ms 183796 KB Output is correct
5 Correct 1074 ms 225620 KB Output is correct
6 Correct 1892 ms 191380 KB Output is correct
7 Correct 1556 ms 75396 KB Output is correct
8 Correct 653 ms 75200 KB Output is correct
9 Correct 524 ms 82180 KB Output is correct
10 Correct 1477 ms 76884 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24408 KB Output is correct
2 Correct 646 ms 42684 KB Output is correct
3 Correct 715 ms 42836 KB Output is correct
4 Correct 624 ms 42896 KB Output is correct
5 Correct 376 ms 43024 KB Output is correct
6 Correct 571 ms 42788 KB Output is correct
7 Correct 689 ms 42852 KB Output is correct
8 Correct 634 ms 42880 KB Output is correct
9 Correct 391 ms 43092 KB Output is correct
10 Correct 547 ms 42820 KB Output is correct
11 Correct 702 ms 42832 KB Output is correct
12 Correct 11 ms 24156 KB Output is correct
13 Correct 1184 ms 186832 KB Output is correct
14 Correct 1825 ms 189504 KB Output is correct
15 Correct 856 ms 183796 KB Output is correct
16 Correct 1074 ms 225620 KB Output is correct
17 Correct 1892 ms 191380 KB Output is correct
18 Correct 1556 ms 75396 KB Output is correct
19 Correct 653 ms 75200 KB Output is correct
20 Correct 524 ms 82180 KB Output is correct
21 Correct 1477 ms 76884 KB Output is correct
22 Correct 2273 ms 200164 KB Output is correct
23 Correct 2045 ms 201676 KB Output is correct
24 Correct 2451 ms 204944 KB Output is correct
25 Correct 2706 ms 208532 KB Output is correct
26 Correct 2807 ms 199452 KB Output is correct
27 Correct 1672 ms 232644 KB Output is correct
28 Correct 1364 ms 197404 KB Output is correct
29 Correct 2841 ms 198224 KB Output is correct
30 Correct 2986 ms 197704 KB Output is correct
31 Correct 2927 ms 198284 KB Output is correct
32 Correct 713 ms 83704 KB Output is correct
33 Correct 784 ms 78268 KB Output is correct
34 Correct 1125 ms 74044 KB Output is correct
35 Correct 1170 ms 74068 KB Output is correct
36 Correct 1421 ms 74664 KB Output is correct
37 Correct 1369 ms 74736 KB Output is correct