oj.uz

답안 #807252

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
807252 2023-08-04T15:16:30 Z hoangnghiep 공장들 (JOI14_factories) C++14
15 / 100
 1904 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[1000005],sparse_table[20][1000005];
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<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))]);
		}
	}
	
	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;
	}
	bool chk = 0;
	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:161:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |  for(int i=0;i<List.size();++i){
      |              ~^~~~~~~~~~~~
factories.cpp:138:7: warning: unused variable 'chk' [-Wunused-variable]
  138 |  bool chk = 0;
      |       ^~~
factories.cpp:185:17: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  185 |  dfs_to_find_sol(root,0);
      |  ~~~~~~~~~~~~~~~^~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 24788 KB Output is correct
2 Correct 765 ms 36236 KB Output is correct
3 Correct 781 ms 36264 KB Output is correct
4 Correct 775 ms 36348 KB Output is correct
5 Correct 728 ms 36632 KB Output is correct
6 Correct 449 ms 36164 KB Output is correct
7 Correct 735 ms 36380 KB Output is correct
8 Correct 744 ms 36304 KB Output is correct
9 Correct 730 ms 36628 KB Output is correct
10 Correct 432 ms 36168 KB Output is correct
11 Correct 754 ms 36380 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 24788 KB Output is correct
2 Correct 765 ms 36236 KB Output is correct
3 Correct 781 ms 36264 KB Output is correct
4 Correct 775 ms 36348 KB Output is correct
5 Correct 728 ms 36632 KB Output is correct
6 Correct 449 ms 36164 KB Output is correct
7 Correct 735 ms 36380 KB Output is correct
8 Correct 744 ms 36304 KB Output is correct
9 Correct 730 ms 36628 KB Output is correct
10 Correct 432 ms 36168 KB Output is correct
11 Correct 754 ms 36380 KB Output is correct
12 Correct 13 ms 24588 KB Output is correct
13 Correct 1497 ms 521772 KB Output is correct
14 Runtime error 1904 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -