Submission #807239

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
807239	2023-08-04T15:10:49 Z	hoangnghiep	Factories (JOI14_factories)	C++14	Compilation error	0 ms	0 KB

factories

#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=5e3;
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[100005],sparse_table[20][100005];
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;
	int 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);
			int 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});
//			cout<<x<<" "<<y<<" "<<w<<endl;
			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);
			int 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});
//			cout<<x<<" "<<y<<" "<<w<<endl;
			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;
}
#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=5e3;
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[100005],sparse_table[20][100005];
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;
	int 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);
			int 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});
//			cout<<x<<" "<<y<<" "<<w<<endl;
			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);
			int 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});
//			cout<<x<<" "<<y<<" "<<w<<endl;
			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: At global scope:
factories.cpp:209:11: error: redefinition of 'const int LIM'
  209 | const int LIM=5e3;
      |           ^~~
factories.cpp:16:11: note: 'const int LIM' previously defined here
   16 | const int LIM=5e3;
      |           ^~~
factories.cpp:210:10: error: redefinition of 'const long long int INF'
  210 | const ll INF=1e18;
      |          ^~~
factories.cpp:17:10: note: 'const long long int INF' previously defined here
   17 | const ll INF=1e18;
      |          ^~~
factories.cpp:211:14: error: redefinition of 'const string name'
  211 | const string name="template";
      |              ^~~~
factories.cpp:18:14: note: 'const string name' previously declared here
   18 | const string name="template";
      |              ^~~~
factories.cpp:212:5: error: redefinition of 'int n'
  212 | int n,m;
      |     ^
factories.cpp:19:5: note: 'int n' previously declared here
   19 | int n,m;
      |     ^
factories.cpp:212:7: error: redefinition of 'int m'
  212 | int n,m;
      |       ^
factories.cpp:19:7: note: 'int m' previously declared here
   19 | int n,m;
      |       ^
factories.cpp:213:13: error: redefinition of 'std::vector<std::pair<int, long long int> > adj [5005]'
  213 | vector<pii> adj[LIM+5],adj_vt[LIM+5];
      |             ^~~
factories.cpp:20:13: note: 'std::vector<std::pair<int, long long int> > adj [5005]' previously declared here
   20 | vector<pii> adj[LIM+5],adj_vt[LIM+5];
      |             ^~~
factories.cpp:213:24: error: redefinition of 'std::vector<std::pair<int, long long int> > adj_vt [5005]'
  213 | vector<pii> adj[LIM+5],adj_vt[LIM+5];
      |                        ^~~~~~
factories.cpp:20:24: note: 'std::vector<std::pair<int, long long int> > adj_vt [5005]' previously declared here
   20 | vector<pii> adj[LIM+5],adj_vt[LIM+5];
      |                        ^~~~~~
factories.cpp:214:5: error: redefinition of 'int time_dfs'
  214 | int time_dfs=0;
      |     ^~~~~~~~
factories.cpp:21:5: note: 'int time_dfs' previously defined here
   21 | int time_dfs=0;
      |     ^~~~~~~~
factories.cpp:215:5: error: redefinition of 'std::pair<int, long long int> euler_tour [100005]'
  215 | pii euler_tour[100005],sparse_table[20][100005];
      |     ^~~~~~~~~~
factories.cpp:22:5: note: 'std::pair<int, long long int> euler_tour [100005]' previously defined here
   22 | pii euler_tour[100005],sparse_table[20][100005];
      |     ^~~~~~~~~~
factories.cpp:215:24: error: redefinition of 'std::pair<int, long long int> sparse_table [20][100005]'
  215 | pii euler_tour[100005],sparse_table[20][100005];
      |                        ^~~~~~~~~~~~
factories.cpp:22:24: note: 'std::pair<int, long long int> sparse_table [20][100005]' previously defined here
   22 | pii euler_tour[100005],sparse_table[20][100005];
      |                        ^~~~~~~~~~~~
factories.cpp:216:5: error: redefinition of 'int tin [5005]'
  216 | int tin[LIM+5],tout[LIM+5],h[LIM+5],low[20][LIM+5];
      |     ^~~
factories.cpp:23:5: note: 'int tin [5005]' previously declared here
   23 | int tin[LIM+5],tout[LIM+5],h[LIM+5],low[20][LIM+5];
      |     ^~~
factories.cpp:216:16: error: redefinition of 'int tout [5005]'
  216 | int tin[LIM+5],tout[LIM+5],h[LIM+5],low[20][LIM+5];
      |                ^~~~
factories.cpp:23:16: note: 'int tout [5005]' previously declared here
   23 | int tin[LIM+5],tout[LIM+5],h[LIM+5],low[20][LIM+5];
      |                ^~~~
factories.cpp:216:28: error: redefinition of 'int h [5005]'
  216 | int tin[LIM+5],tout[LIM+5],h[LIM+5],low[20][LIM+5];
      |                            ^
factories.cpp:23:28: note: 'int h [5005]' previously declared here
   23 | int tin[LIM+5],tout[LIM+5],h[LIM+5],low[20][LIM+5];
      |                            ^
factories.cpp:216:37: error: redefinition of 'int low [20][5005]'
  216 | int tin[LIM+5],tout[LIM+5],h[LIM+5],low[20][LIM+5];
      |                                     ^~~
factories.cpp:23:37: note: 'int low [20][5005]' previously declared here
   23 | int tin[LIM+5],tout[LIM+5],h[LIM+5],low[20][LIM+5];
      |                                     ^~~
factories.cpp:217:4: error: redefinition of 'long long int up_weight [20][5005]'
  217 | ll up_weight[20][LIM+5],dist_X[LIM+5],dist_Y[LIM+5];
      |    ^~~~~~~~~
factories.cpp:24:4: note: 'long long int up_weight [20][5005]' previously declared here
   24 | ll up_weight[20][LIM+5],dist_X[LIM+5],dist_Y[LIM+5];
      |    ^~~~~~~~~
factories.cpp:217:25: error: redefinition of 'long long int dist_X [5005]'
  217 | ll up_weight[20][LIM+5],dist_X[LIM+5],dist_Y[LIM+5];
      |                         ^~~~~~
factories.cpp:24:25: note: 'long long int dist_X [5005]' previously declared here
   24 | ll up_weight[20][LIM+5],dist_X[LIM+5],dist_Y[LIM+5];
      |                         ^~~~~~
factories.cpp:217:39: error: redefinition of 'long long int dist_Y [5005]'
  217 | ll up_weight[20][LIM+5],dist_X[LIM+5],dist_Y[LIM+5];
      |                                       ^~~~~~
factories.cpp:24:39: note: 'long long int dist_Y [5005]' previously declared here
   24 | ll up_weight[20][LIM+5],dist_X[LIM+5],dist_Y[LIM+5];
      |                                       ^~~~~~
factories.cpp:218:13: error: redefinition of 'std::vector<int> List'
  218 | vector<int> List;
      |             ^~~~
factories.cpp:25:13: note: 'std::vector<int> List' previously declared here
   25 | vector<int> List;
      |             ^~~~
factories.cpp:219:5: error: redefinition of 'int color [5005]'
  219 | int color[LIM+5];
      |     ^~~~~
factories.cpp:26:5: note: 'int color [5005]' previously declared here
   26 | int color[LIM+5];
      |     ^~~~~
factories.cpp:220:13: error: redefinition of 'std::vector<int> st'
  220 | vector<int> st;
      |             ^~
factories.cpp:27:13: note: 'std::vector<int> st' previously declared here
   27 | vector<int> st;
      |             ^~
factories.cpp:221:6: error: redefinition of 'void dfs(int, int, int)'
  221 | void dfs(int u,int parent,int depth){
      |      ^~~
factories.cpp:28:6: note: 'void dfs(int, int, int)' previously defined here
   28 | void dfs(int u,int parent,int depth){
      |      ^~~
factories.cpp:242:5: error: redefinition of 'int lca(int, int)'
  242 | int lca(int u,int v){
      |     ^~~
factories.cpp:49:5: note: 'int lca(int, int)' previously defined here
   49 | int lca(int u,int v){
      |     ^~~
factories.cpp:251:4: error: redefinition of 'long long int lift_weight(int, int)'
  251 | ll lift_weight(int u,int k){
      |    ^~~~~~~~~~~
factories.cpp:58:4: note: 'long long int lift_weight(int, int)' previously defined here
   58 | ll lift_weight(int u,int k){
      |    ^~~~~~~~~~~
factories.cpp:265:6: error: redefinition of 'bool cmp(int, int)'
  265 | bool cmp(int a,int b){
      |      ^~~
factories.cpp:72:6: note: 'bool cmp(int, int)' previously defined here
   72 | bool cmp(int a,int b){
      |      ^~~
factories.cpp:269:6: error: redefinition of 'bool isSubtree(int, int)'
  269 | bool isSubtree(int u,int v)
      |      ^~~~~~~~~
factories.cpp:76:6: note: 'bool isSubtree(int, int)' previously defined here
   76 | bool isSubtree(int u,int v)
      |      ^~~~~~~~~
factories.cpp:273:6: error: redefinition of 'void dfs_to_find_sol(int, int)'
  273 | void dfs_to_find_sol(int u,int parent){
      |      ^~~~~~~~~~~~~~~
factories.cpp:80:6: note: 'void dfs_to_find_sol(int, int)' previously defined here
   80 | void dfs_to_find_sol(int u,int parent){
      |      ^~~~~~~~~~~~~~~
factories.cpp:281:6: error: redefinition of 'void Init(int, int*, int*, int*)'
  281 | void Init(int N, int A[], int B[], int D[]){
      |      ^~~~
factories.cpp:88:6: note: 'void Init(int, int*, int*, int*)' previously defined here
   88 | void Init(int N, int A[], int B[], int D[]){
      |      ^~~~
factories.cpp:317:11: error: redefinition of 'long long int Query(int, int*, int, int*)'
  317 | long long Query(int S, int X[], int T, int Y[]){
      |           ^~~~~
factories.cpp:124:11: note: 'long long int Query(int, int*, int, int*)' previously defined here
  124 | long long Query(int S, int X[], int T, int Y[]){
      |           ^~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:354:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  354 |  for(int i=0;i<List.size();++i){
      |              ~^~~~~~~~~~~~
factories.cpp:331:7: warning: unused variable 'chk' [-Wunused-variable]
  331 |  bool chk = 0;
      |       ^~~