Submission #750565

#	Time	Username	Problem	Language	Result	Execution time	Memory
750565		jmyszka2007	Factories (JOI14_factories)	C++17	15 / 100	8102 ms	524288 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];
unordered_map<int, ll>dist[LIM + 10];
unordered_map<int, ll>cnt;
int siz[LIM + 10];
int oj[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) {
	for(auto x : g[v]) {
		if(x.st != o && !vis[x.st]) {
			dist[kt][x.st] = dist[kt][v] + x.nd;
			cntdist(x.st, v, kt);
		}
	}
}
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 o) {
	int c = find(v);
	oj[c] = o;
	vis[c] = 1;
	cntdist(c, c, c);
	for(auto x : g[c]) {
		if(!vis[x.st]) {
			dfs(x.st, c);
		}
	}
}
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]});
	}
	cntsiz(1, 1);
	dfs(1, -1);
}
ll Query(int n, int a[], int m, int b[]) {
	for(int i = 0; i < n; i++) {
		int tmp = a[i];
		while(tmp != -1) {
			if(cnt.count(tmp)) {
				cnt[tmp] = min(cnt[tmp], dist[tmp][a[i]]);
			}
			else {
				cnt[tmp] = dist[tmp][a[i]];
			}
			tmp = oj[tmp];
		}
	}
	ll ans = 1e18;
	for(int i = 0; i < m; i++) {
		int tmp = b[i];
		while(tmp != -1) {
			if(cnt.count(tmp)) {
				ans = min(ans, cnt[tmp] + dist[tmp][b[i]]);
			}
			tmp = oj[tmp];
		}
	}
	cnt.clear();
	return ans;
}

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