Submission #397947

#	Time	Username	Problem	Language	Result	Execution time	Memory
397947		keta_tsimakuridze	Factories (JOI14_factories)	C++14	100 / 100	5218 ms	180996 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int NN=5e5+5;
const long long Inf=1e15;
int sz[NN],par[NN],H[NN],fix[NN];
long long dist[NN][20],mn[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++){
		A[i]++;
		B[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++){
		X[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];
		}
	}
	long long ans = Inf;
	for(int i =0;i<T;i++){
		Y[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 (stderr)

factories.cpp: In function 'void get_sz(int, int)':
factories.cpp:13:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'void dfs(int, int, int)':
factories.cpp:25:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'void centroid_decomp(int, int, int)':
factories.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=0;i<V[c].size();i++){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:74:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for(int i=0;i<remove.size();i++){
      |              ~^~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67