Submission #397940

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
397940	2021-05-03T12:07:54 Z	keta_tsimakuridze	Factories (JOI14_factories)	C++14	Compilation error	0 ms	0 KB

factories

//#include "factories.h"
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int NN=5e5+5,Inf=1e15;
int sz[NN],dist[NN][20],H[NN],mn[NN],par[NN],fix[NN];
vector<pair<int,int> >V[NN];
void get_sz(int u,int p){
	sz[u] = 1;
	for(int i=0;i<V[u].size();i++){
		if(V[u][i].f!=p && !fix[V[u][i].f]) get_sz(V[u][i].f,u),sz[u]+=sz[V[u][i].f];
	}
}
int find_centroid(int u,int p,int Sz){
	for(int i=0;i<V[u].size();i++){
		if(V[u][i].f==p || fix[V[u][i].f]) continue;
		if(sz[V[u][i].f] > Sz/2) return find_centroid(V[u][i].f,u,Sz);
	}
	return u;
}
void dfs(int u,int p,int h){
	for(int i=0;i<V[u].size();i++){
		if(V[u][i].f==p || fix[V[u][i].f]) continue;	
		dist[V[u][i].f][h] = dist[u][h] + V[u][i].s;	
		dfs(V[u][i].f,u,h);
	}
}
void centroid_decomp(int u,int p,int h){
	get_sz(u,0); 
	int c = find_centroid(u,0,sz[u]);
	par[c] = p;
	H[c] = h;
	mn[c] =Inf;
	dfs(c,0,h);
	fix[c] = 1;
	for(int i=0;i<V[c].size();i++){
		if(!fix[V[c][i].f]) centroid_decomp(V[c][i].f,c,h+1);
	}
}
void Init(int N, int A[], int B[], int D[]) {
	for(int i=0;i<N-1;i++){
		V[A[i]].push_back({B[i],D[i]});
		V[B[i]].push_back({A[i],D[i]});
	}
	centroid_decomp(1,0,0);
}

long long Query(int S, int X[], int T, int Y[]) {
	
	vector<int> remove;
	for(int i=0;i<S;i++){
		int c = X[i];
		while(c!=0){
			if(mn[c] == Inf)remove.push_back(c);
			mn[c] = min(mn[c],dist[X[i]][H[c]]);
			c=par[c];
		}
	}
	int ans = Inf;
	for(int i =0;i<T;i++){
		int c = Y[i];
		while(c!=0){
			ans = min(mn[c] + dist[Y[i]][H[c]],ans);
			c=par[c];
		}		
	}
	for(int i=0;i<remove.size();i++){
		mn[remove[i]]=Inf;
	}
  return ans;
}

Compilation message

factories.cpp: In function 'void get_sz(long long int, long long int)':
factories.cpp:12:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'long long int find_centroid(long long int, long long int, long long int)':
factories.cpp:17:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'void dfs(long long int, long long int, long long int)':
factories.cpp:24:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'void centroid_decomp(long long int, long long int, long long int)':
factories.cpp:38:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(int i=0;i<V[c].size();i++){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'long long int Query(long long int, long long int*, long long int, long long int*)':
factories.cpp:69:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i=0;i<remove.size();i++){
      |              ~^~~~~~~~~~~~~~
/tmp/cc95N6oN.o: In function `main':
grader.cpp:(.text.startup+0x37b): undefined reference to `Init(int, int*, int*, int*)'
grader.cpp:(.text.startup+0x412): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status