Submission #378412

#	Time	Username	Problem	Language	Result	Execution time	Memory
378412		badont	Factories (JOI14_factories)	C++14	100 / 100	7664 ms	500704 KiB

factories

#include<bits/stdc++.h>
#include"factories.h"
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<LL,LL> pii;
typedef pair<LL,pii> ppi;
typedef pair<pii,pii> ppp;
#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {cout << "["; F0R(i, v.size()) {if (i) cout << ", "; cout << v[i];} return cout << "]";}

const LL INF = 1e17;

struct centroid{
	LL mn = INF;
	LL mn2 = INF;
	LL mnch = -1;
};

struct parcen{
	LL depth;
	LL parent;
	LL pphead;
};

//var 
LL n, c, sub[500005], v[500005], dep[500005];
vector<pii> e[500005];
centroid cc[500005];
vector<parcen> pc[500005];
//int N, A[500005], B[500005], C[500005], S, T, X[500005], Y[500005], Q;

void dfs_sub(LL g, LL p){
	sub[g] = 1;
	for(auto u : e[g]){
		if(v[u.s] || u.s == p) continue;
		dfs_sub(u.s, g);
		sub[g] += sub[u.s];
	}
}

LL cen(LL g, LL p, LL sz){
	for(auto u : e[g]){
		if(u.s == p || v[u.s]) continue;
		if(sub[u.s] * 2 > sz) return cen(u.s, g, sz);
	}
	return g;
}

void dfs_dep(LL g, LL p, LL d, LL pp = 0){
	dep[g] = d;
	parcen tt;
	if(p == c) pp = g;
	tt.depth = d;
	tt.parent = c;
	tt.pphead = pp;
	pc[g].pb(tt);
	for(auto u : e[g]){
		if(u.s == p || v[u.s]) continue;
		dfs_dep(u.s, g, d + u.f, pp);
	}
}

void make_tree(LL g, LL sz){
	dfs_sub(g, 0);
	c = cen(g, 0, sz);
	dfs_sub(c, 0);
	dfs_dep(c, 0, 0);

	v[c] = 1;
	for(auto u : e[c]){
		if(v[u.s]) continue;
		make_tree(u.s, sub[u.s]);
	}
}

void Init(int N, int A[], int B[], int C[]){
	n = N;
	F0R(i, n-1){
		e[A[i]+1].pb({C[i], B[i]+1});
		e[B[i]+1].pb({C[i], A[i]+1});
	}

	make_tree(1, n);
}

LL Query(int S, int X[], int T, int Y[]){
	F0R(i, S){
		for(auto u : pc[X[i]+1]){
			centroid& x = cc[u.parent];
			if(x.mnch == u.pphead)
				x.mn = min(x.mn, u.depth);
			else{
				if(u.depth < x.mn){
					x.mn2 = x.mn;
					x.mn = u.depth;
					x.mnch = u.pphead;
				}
				else if(u.depth < x.mn2)
					x.mn2 = u.depth;
			}
		}
	}

	LL ans = INF;
	F0R(i, T){
		for(auto u: pc[Y[i] + 1]){
			centroid x = cc[u.parent];
			if(u.pphead == x.mnch)
				ans = min(ans, u.depth + x.mn2);
			else ans = min(ans, u.depth + x.mn);
		}
	}

	F0R(i, S){
		for(auto u : pc[X[i] + 1]){
			centroid& x = cc[u.parent];
			x.mnch = -1;
			x.mn = INF;
			x.mn2 = INF;
		}
	}

	return ans;
}

/*int main(){
	ios_base::sync_with_stdio(0); 
	cin.tie(0);

	cin >> N >> Q;
	F0R(i, N-1) cin >> A[i] >> B[i] >> C[i];
	Init(N, A, B, C);
	F0R(i, Q){
		cin >> S >> T;
		F0R(i, S) cin >> X[i];
		F0R(i, T) cin >> Y[i];
		cout << Query(S, X, T, Y) << '\n';
	}

	cout.flush();
	return 0;
}*/

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