Submission #240117

#	Time	Username	Problem	Language	Result	Execution time	Memory
240117		frodakcin	Factories (JOI14_factories)	C++11	100 / 100	6329 ms	331592 KiB

factories

#include "factories.h"

#include <cstring>
#include <vector>

template<typename T> bool ckmax(T& a, T b){return a<b?a=b,1:0;}
template<typename T> bool ckmin(T& a, T b){return b<a?a=b,1:0;}

using ll = long long;

const ll INF = 0x3f3f3f3f3f3f3f3f;
const int MN = 5e5+10;

struct edge{public: int n,w;};
std::vector<edge> a[MN];
struct group{public: int c;ll d;};
std::vector<group> g[MN];
int s[MN];
bool r[MN];
ll ans, bt[MN], bs[MN];

int dfs(int n, int p=-1)
{
	s[n]=1;
	for(auto x:a[n])
		if(!r[x.n]&&x.n!=p)
			s[n]+=dfs(x.n, n);
	return s[n];
}
int get_centroid(int n, int ms, int p=-1)
{
	for(auto x:a[n])
		if(!r[x.n]&&x.n!=p)
			if(s[x.n]*2>=ms)
				return get_centroid(x.n, ms, n);
	return n;
}
int top;
void dfs2(int n, int p=-1, ll d=0)
{
	g[n].push_back({top, d});
	for(auto x:a[n])
		if(!r[x.n]&&x.n!=p)
			dfs2(x.n, n, d+x.w);
}
void work(int n)
{
	int c=get_centroid(n, dfs(n));
	top=c;
	dfs2(c);
	r[c]=1;
	for(auto x:a[c])
		if(!r[x.n])
			work(x.n);
}
void Init(int N, int A[], int B[], int D[])
{
	for(int i=0;i+1<N;++i)
		a[A[i]].push_back({B[i], D[i]}), a[B[i]].push_back({A[i], D[i]});
	work(0);
	memset(bs, 0x3f, sizeof bs);
	memset(bt, 0x3f, sizeof bt);
}

long long Query(int S, int X[], int T, int Y[])
{
	ans=INF;
	for(int i=0;i<S;++i)
		for(auto x:g[X[i]])
			ckmin(bs[x.c], x.d);
	for(int i=0;i<T;++i)
		for(auto x:g[Y[i]])
			ckmin(bt[x.c], x.d), ckmin(ans, bs[x.c]+bt[x.c]);
	for(int i=0;i<S;++i)
		for(auto x:g[X[i]])
			bs[x.c]=bt[x.c]=INF;
	for(int i=0;i<T;++i)
		for(auto x:g[Y[i]])
			bs[x.c]=bt[x.c]=INF;
  return ans;
}

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