oj.uz

답안 #807262

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
807262 2023-08-04T15:20:06 Z hoangnghiep 공장들 (JOI14_factories) C++14
15 / 100
 1651 ms 524288 KB 
#include<bits/stdc++.h>
#include "factories.h"
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define f first
#define s second
#define pii pair<int,ll>
#define piii pair<int,pair<int,int>>
#define vii vector<vector<int>>
#define vi vector<int>
#define cd complex<double>
#define endl '\n'
//#define multipletest
using namespace std;
const int LIM=5e5;
const ll INF=1e18;
const string name="template";
int n,m;
vector<pii> adj[LIM+5],adj_vt[LIM+5];
int time_dfs=0;
pii euler_tour[5000005],sparse_table[20][5000005];
int tin[LIM+5],tout[LIM+5],h[LIM+5],low[20][LIM+5];
ll up_weight[20][LIM+5],dist_X[LIM+5],dist_Y[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};
	
	low[0][u] = parent;
	 
	for(auto v:adj[u]){
		if(v.f==parent) continue;
		dfs(v.f,u,depth + 1);
		
		euler_tour[time_dfs++] = {depth,u};
		
		up_weight[0][v.f] = v.s;	
	}
	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 lift_weight(int u,int k){
	int tmp=0;
	ll w = 0;
	while(k>0){
		if(k%2==1){
			w+=up_weight[tmp][u];
			u=low[tmp][u];
		}
		k>>=1;
		tmp++;
	}
	return w;
}
 
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;
		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<22;++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))]);
		}
	}
	
	for(int i=1;i<20;++i){
		for(int j=1;j<=n;++j){
			low[i][j] =low[i-1][low[i-1][j]];
			up_weight[i][j] = up_weight[i-1][j] + up_weight[i-1][low[i-1][j]];
		}
	}
}
 
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();
			int LCA = lca(x,y);
			ll w=lift_weight(x,h[x] - h[LCA]) + lift_weight(y,h[y] - h[LCA]);
			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();
			int LCA = lca(x,y);
			ll w=lift_weight(x,h[x] - h[LCA]) + lift_weight(y,h[y] - h[LCA]);
			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:160:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |  for(int i=0;i<List.size();++i){
      |              ~^~~~~~~~~~~~
factories.cpp:184:17: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  184 |  dfs_to_find_sol(root,0);
      |  ~~~~~~~~~~~~~~~^~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 24824 KB Output is correct
2 Correct 739 ms 36276 KB Output is correct
3 Correct 749 ms 36260 KB Output is correct
4 Correct 755 ms 36312 KB Output is correct
5 Correct 699 ms 36788 KB Output is correct
6 Correct 440 ms 36172 KB Output is correct
7 Correct 740 ms 36392 KB Output is correct
8 Correct 734 ms 36296 KB Output is correct
9 Correct 708 ms 36556 KB Output is correct
10 Correct 463 ms 36164 KB Output is correct
11 Correct 733 ms 36388 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 24692 KB Output is correct
2 Correct 1370 ms 521860 KB Output is correct
3 Runtime error 1651 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 24824 KB Output is correct
2 Correct 739 ms 36276 KB Output is correct
3 Correct 749 ms 36260 KB Output is correct
4 Correct 755 ms 36312 KB Output is correct
5 Correct 699 ms 36788 KB Output is correct
6 Correct 440 ms 36172 KB Output is correct
7 Correct 740 ms 36392 KB Output is correct
8 Correct 734 ms 36296 KB Output is correct
9 Correct 708 ms 36556 KB Output is correct
10 Correct 463 ms 36164 KB Output is correct
11 Correct 733 ms 36388 KB Output is correct
12 Correct 13 ms 24692 KB Output is correct
13 Correct 1370 ms 521860 KB Output is correct
14 Runtime error 1651 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -