Submission #750579

#	Time	Username	Problem	Language	Result	Execution time	Memory
750579		jmyszka2007	Factories (JOI14_factories)	C++17	100 / 100	3689 ms	375648 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef long long ll;
constexpr int LIM = 5e5;
vector<pair<int, int> >g[LIM + 10];
vector<pair<int, ll> >cen[LIM + 10];
ll cnt[LIM + 10];
int siz[LIM + 10];
bool vis[LIM + 10];
void cntsiz(int v, int o) {
	siz[v] = 1;
	for(auto x : g[v]) {
		if(x.st != o) {
			cntsiz(x.st, v);
			siz[v] += siz[x.st];
		}
	}
}
void cntdist(int v, int o, int kt, ll d) {
	cen[v].push_back({kt, d});
	for(auto x : g[v]) {
		if(x.st != o && !vis[x.st]) {
			cntdist(x.st, v, kt, d + x.nd);
		}
	}
}
int find(int a) {
	for(auto x : g[a]) {
		if(!vis[x.st] && siz[x.st] > siz[a] / 2) {
			int tmp = siz[x.st];
			siz[x.st] = siz[a];
			siz[a] -= tmp;
			return find(x.st);
		}
	}
	return a;
}
void dfs(int v) {
	int c = find(v);
	vis[c] = 1;
	cntdist(c, c, c, 0);
	for(auto x : g[c]) {
		if(!vis[x.st]) {
			dfs(x.st);
		}
	}
}
void Init(int n, int a[], int b[], int c[]) {
	for(int i = 0; i < n - 1; i++) {
		g[a[i]].push_back({b[i], c[i]});
		g[b[i]].push_back({a[i], c[i]});
	}
	for(int i = 0; i < n; i++) {
		cnt[i] = 1e18;
	}
	cntsiz(1, 1);
	dfs(1);
}
ll Query(int n, int a[], int m, int b[]) {
	vector<int>vs;
	for(int i = 0; i < n; i++) {
		for(auto x : cen[a[i]]) {
			cnt[x.st] = min(cnt[x.st], x.nd);
			vs.push_back(x.st);
		}
	}
	ll ans = 1e18;
	for(int i = 0; i < m; i++) {
		for(auto x : cen[b[i]]) {
			ans = min(ans, cnt[x.st] + x.nd);
		}
	}
	for(auto x : vs) {
		cnt[x] = 1e18;
	}
	return ans;
}

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