oj.uz

Submission #807291

# Submission time Handle Problem Language Result Execution time Memory
807291 2023-08-04T15:34:42 Z hoangnghiep Factories (JOI14_factories) C++14
100 / 100
 2713 ms 473696 KB 
#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
#define pii pair<int,ll> 
#define f first
#define s second
//#define multipletest
using namespace std;
const int LIM=5e5;
const ll INF=1e18;
int n,m;
vector<pii> adj[LIM+5],adj_vt[LIM+5];
int time_dfs=0;
pii euler_tour[2*LIM+5],sparse_table[20][2*LIM+5];
int tin[LIM+5],tout[LIM+5],h[LIM+5];
ll dist_X[LIM+5],dist_Y[LIM+5],dist[LIM+5];
vector<int> List;
int color[LIM+5];
vector<int> st;
void dfs(int u,int parent,int depth){
 
	h[u] = depth;
	
	tin[u] = time_dfs;
	
	euler_tour[time_dfs++] = {depth,u};
	
	 
	for(auto v:adj[u]){
		if(v.f==parent) continue;
		dist[v.f] = dist[u] + v.s;
		dfs(v.f,u,depth + 1);
		euler_tour[time_dfs++] = {depth,u};
	}
	tout[u] = time_dfs;
}
 
int lca(int u,int v){
	if(tin[u]>tin[v]){
		swap(u,v);
	}
	int bt = 31 - __builtin_clz(tin[v]-tin[u]+1);
	pii mn = min(sparse_table[bt][tin[u]],sparse_table[bt][tin[v] - (1<<bt) + 1]);
	return mn.s;
}
 
ll Dist(int u,int v){
	int LCA = lca(u,v);
	return dist[u] +  dist[v]- 2*dist[LCA];
} 
bool cmp(int a,int b){
	return tin[a]<tin[b];
}
 
bool isSubtree(int u,int v)
{
	return tin[u]<=tin[v] && tin[v]<=tout[u];
}
void dfs_to_find_sol(int u,int parent){
	for(auto v:adj_vt[u]){
		if(v.f==parent) continue;
		dfs_to_find_sol(v.f,u);
		dist_X[u] = min(dist_X[u],dist_X[v.f] + v.s);
		dist_Y[u] = min(dist_Y[u],dist_Y[v.f] + v.s);
	}
}
void Init(int N, int A[], int B[], int D[]){
	n=N;
	for(int i=0;i<n-1;++i){
		A[i]++;
		B[i]++;
	}
	for(int i=0;i<n-1;++i){
		adj[A[i]].push_back({B[i],D[i]});
		adj[B[i]].push_back({A[i],D[i]});
	}
	for(int i=1;i<=n;++i){
		dist_X[i]=INF;
		dist_Y[i]=INF;
		dist[i]=0;
		color[i] = -1;
	}
	
	dfs(1,0,0);
	
	for(int i=0;i<time_dfs;++i){
		sparse_table[0][i]  = euler_tour[i];
	}
	
 	for(int i=1;i<20;++i){
		for(int j=0;j+(1<<i)-1<time_dfs;++j){
			sparse_table[i][j] = min(sparse_table[i-1][j],sparse_table[i-1][j + (1<<(i-1))]);
		}
	}	
}
 
long long Query(int S, int X[], int T, int Y[]){
	for(auto x:List){
		color[x] = -1;
		adj_vt[x].clear();
		dist_X[x]=dist_Y[x]=INF;
	}
	List.clear();
	st.clear();
    for(int i=0;i<S;++i){
    	List.push_back(++X[i]);
    	color[X[i]] = 0;
    	dist_X[X[i]]=0;
    	dist_Y[X[i]]=INF;
	}
	for(int i=0;i<T;++i){
		List.push_back(++Y[i]);
		if(color[Y[i]]==0){
			return 0;
		}
		color[Y[i]]=1;
		dist_X[Y[i]]=INF;
		dist_Y[Y[i]]=0;
	}
		
	sort(List.begin(),List.end(),cmp);
	for(int i=1;i<S+T;++i){
		int LCA = lca(List[i-1],List[i]);
		if(color[LCA]==-1){
			dist_X[LCA] = dist_Y[LCA]  =  INF;
		}
		List.push_back(LCA);
	}
	
	int root;
	sort(List.begin(),List.end(),cmp);
	List.erase(unique(List.begin(),List.end()),List.end());
	for(int i=0;i<List.size();++i){
		int u = List[i];
		while(st.size()>=2 && !isSubtree(st.back(),u)){
			int x = st[st.size()-2];
			int y= st.back();
			ll w=Dist(x,y);
			adj_vt[x].push_back({y,w});
			adj_vt[y].push_back({x,w});
			root=x;
			st.pop_back();
		}
		st.push_back(u);
	}
	while(st.size()>=2){
			int x = st[st.size()-2];
			int y= st.back();
			ll w=Dist(x,y);
			adj_vt[x].push_back({y,w});
			adj_vt[y].push_back({x,w});
			root=x;
			st.pop_back();
	}
	dfs_to_find_sol(root,0);
	ll ans=INF;
    for(auto x:List){
    	ans = min(ans,dist_X[x] + dist_Y[x]);
	}
   	return ans;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:133:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |  for(int i=0;i<List.size();++i){
      |              ~^~~~~~~~~~~~
factories.cpp:155:17: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  155 |  dfs_to_find_sol(root,0);
      |  ~~~~~~~~~~~~~~~^~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24404 KB Output is correct
2 Correct 706 ms 34764 KB Output is correct
3 Correct 745 ms 34824 KB Output is correct
4 Correct 709 ms 34848 KB Output is correct
5 Correct 672 ms 35112 KB Output is correct
6 Correct 432 ms 34688 KB Output is correct
7 Correct 699 ms 34848 KB Output is correct
8 Correct 696 ms 34832 KB Output is correct
9 Correct 667 ms 35168 KB Output is correct
10 Correct 428 ms 34740 KB Output is correct
11 Correct 678 ms 34888 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24148 KB Output is correct
2 Correct 1262 ms 408300 KB Output is correct
3 Correct 1280 ms 430324 KB Output is correct
4 Correct 979 ms 424040 KB Output is correct
5 Correct 1114 ms 466236 KB Output is correct
6 Correct 1253 ms 432692 KB Output is correct
7 Correct 1055 ms 117236 KB Output is correct
8 Correct 641 ms 116532 KB Output is correct
9 Correct 688 ms 123048 KB Output is correct
10 Correct 981 ms 118876 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24404 KB Output is correct
2 Correct 706 ms 34764 KB Output is correct
3 Correct 745 ms 34824 KB Output is correct
4 Correct 709 ms 34848 KB Output is correct
5 Correct 672 ms 35112 KB Output is correct
6 Correct 432 ms 34688 KB Output is correct
7 Correct 699 ms 34848 KB Output is correct
8 Correct 696 ms 34832 KB Output is correct
9 Correct 667 ms 35168 KB Output is correct
10 Correct 428 ms 34740 KB Output is correct
11 Correct 678 ms 34888 KB Output is correct
12 Correct 12 ms 24148 KB Output is correct
13 Correct 1262 ms 408300 KB Output is correct
14 Correct 1280 ms 430324 KB Output is correct
15 Correct 979 ms 424040 KB Output is correct
16 Correct 1114 ms 466236 KB Output is correct
17 Correct 1253 ms 432692 KB Output is correct
18 Correct 1055 ms 117236 KB Output is correct
19 Correct 641 ms 116532 KB Output is correct
20 Correct 688 ms 123048 KB Output is correct
21 Correct 981 ms 118876 KB Output is correct
22 Correct 2485 ms 443008 KB Output is correct
23 Correct 2229 ms 444556 KB Output is correct
24 Correct 2713 ms 447136 KB Output is correct
25 Correct 2527 ms 450592 KB Output is correct
26 Correct 2430 ms 442216 KB Output is correct
27 Correct 2606 ms 473696 KB Output is correct
28 Correct 1701 ms 438232 KB Output is correct
29 Correct 2390 ms 441004 KB Output is correct
30 Correct 2298 ms 440256 KB Output is correct
31 Correct 2355 ms 440912 KB Output is correct
32 Correct 1149 ms 124876 KB Output is correct
33 Correct 787 ms 120052 KB Output is correct
34 Correct 1294 ms 115916 KB Output is correct
35 Correct 1169 ms 115744 KB Output is correct
36 Correct 1334 ms 116664 KB Output is correct
37 Correct 1305 ms 116596 KB Output is correct