Submission #1054080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054080		tamir1	Factories (JOI14_factories)	C++17	100 / 100	5089 ms	152880 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
#define ff first
#define ss second
using namespace std;
const ll INF=1e18;
ll dis[500001],c[500001];
int jump[21][500001],dep[500001],par[500001],sz[500001],n;
vector<pair<int,ll>> v[500001];
queue<int> q;
bitset<500001> ok; 
void dfs(int x,int y){
	int nx;
	ll len;
	jump[0][x]=y;
	for(int i=0;i<v[x].size();i++){
		nx=v[x][i].ff;
		if(nx==y) continue;
		len=v[x][i].ss;
		dep[nx]=dep[x]+1;
		dis[nx]=dis[x]+len;
		dfs(nx,x);
	}
}
int up(int x,int k){
	for(int i=0;i<=20;i++){
		if(k&(1<<i)) x=jump[i][x];
	}
	return x;
}
int lca(int x,int y){
	if(dep[x]>dep[y]) swap(x,y);
	y=up(y,dep[y]-dep[x]);
	if(x==y) return x;
	for(int i=20;i>=0;i--){
		if(jump[i][x]!=jump[i][y]){
			x=jump[i][x];
			y=jump[i][y];
		}
	}
	return jump[0][x];
}
ll dist(int x,int y){
	return dis[x]+dis[y]-dis[lca(x,y)]*2;
}
int sze(int x,int y){
	sz[x]=1;
	for(int i=0;i<v[x].size();i++){
		int z=v[x][i].ff;
		if(z==y || ok[z]) continue;
		sz[x]+=sze(z,x);
	}
	return sz[x];
}
int centroid(int x,int y,int n){
	for(int i=0;i<v[x].size();i++){
		int z=v[x][i].ff;
		if(z==y || ok[z]) continue;
		if(sz[z]>n/2) return centroid(z,x,n);
	}
	return x;
}
void build(int x,int y){
	int cnt=centroid(x,y,sze(x,y));
	ok[cnt]=1;
	par[cnt]=y;
	for(int i=0;i<v[cnt].size();i++){
		int z=v[cnt][i].ff;
		if(!ok[z]) build(z,cnt);
	}
}
void Init(int N, int A[], int B[], int D[]) {
	n=N;
	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]});
	}
	dfs(0,0);
	for(int j=1;j<=20;j++){
		for(int i=0;i<N;i++){
			jump[j][i]=jump[j-1][jump[j-1][i]];
		}
	}
	build(0,-1);
	for(int i=0;i<N;i++) c[i]=INF;
}
long long Query(int S, int X[], int T, int Y[]) {
	ll res=INF;
	for(int i=0;i<S;i++){
		int x=X[i],y;
		y=x;
		while(y!=-1){
			c[y]=min(c[y],dist(x,y));
			q.push(y);
			y=par[y];
		}
	}
	for(int i=0;i<T;i++){
		int x=Y[i],y;
		y=x;
		while(y!=-1){
			res=min(res,dist(x,y)+c[y]);
			y=par[y];
		}
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		c[x]=INF;
	}
	return res;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:17:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'int sze(int, int)':
factories.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'int centroid(int, int, int)':
factories.cpp:57:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'void build(int, int)':
factories.cpp:68:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(int i=0;i<v[cnt].size();i++){
      |              ~^~~~~~~~~~~~~~

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