Submission #1281059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281059		Jawad_Akbar_JJ	Factories (JOI14_factories)	C++20	100 / 100	1349 ms	124712 KiB

factories

#include <iostream>
#include <vector>
#include "factories.h"
#include <algorithm>

using namespace std;
const int M = 500005;
vector<pair<int,int>> nei[M];
int hei[M], par[M][20], st[M], en[M], ind, cur = 1;
long long Min[M][2], dist[M], inf = 1e17, Ans;

void dfs0(int u, int p){
	hei[u] = (p == -1 ? 0 : hei[p]) + 1;
	par[u][0] = p;
	for (int i=1;i<20;i++)
		par[u][i] = (par[u][i-1] == -1 ? -1 : par[par[u][i-1]][i-1]);

	st[u] = cur++;
	for (auto [i, w] : nei[u]){
		if (i == p)
			continue;
		dist[i] = dist[u] + w;
		dfs0(i, u);
	}
	Min[u][0] = Min[u][1] = inf;
	en[u] = cur;
}

void Init(int n, int a[], int b[], int c[]){
	for (int i=0;i<n-1;i++){
		nei[a[i]].push_back({b[i], c[i]});
		nei[b[i]].push_back({a[i], c[i]});
	}

	dfs0(0, -1);
}

int moveUp(int v, int d){
	for (int i=0;i<20;i++)
		if ((1<<i) & d)
			v = par[v][i];
	return v;
}

int LCA(int u, int v){
	if (hei[u] > hei[v])
		swap(u, v);
	v = moveUp(v, hei[v] - hei[u]);

	if (v == u)
		return v;
	for (int i=19;i>=0;i--)
		if (par[v][i] != par[u][i])
			u = par[u][i], v = par[v][i];
	return par[u][0];
}

void merge(int a, int b, long long c){
	Ans = min(Ans, min(Min[a][1] + Min[b][0], Min[b][1] + Min[a][0]) + c);
	Min[a][1] = min(Min[a][1], Min[b][1] + c);
	Min[a][0] = min(Min[a][0], Min[b][0] + c);
}

void dfs(vector<pair<int,int>> &t2, int u){
	while (ind < t2.size() and t2[ind].first < en[u]){
		int v = t2[ind++].second;
		dfs(t2, v);

		merge(u, v, dist[v] - dist[u]);
	}
}

long long Query(int s, int x[], int t, int y[]){
	Ans = inf;
	vector<pair<int,int>> t2;
	for (int i=0;i<s;i++)
		t2.push_back({st[x[i]], x[i]}), Min[x[i]][0] = 0, Min[x[i]][1] = inf;
	for (int i=0;i<t;i++)
		t2.push_back({st[y[i]], y[i]}), Min[y[i]][1] = 0, Min[y[i]][0] = inf;

	sort(begin(t2), end(t2));

	for (int i=1;i<s+t;i++){
		if (t2[i-1] == t2[i])
			Ans = 0;
		int lca = LCA(t2[i-1].second, t2[i].second);
		t2.push_back({st[lca], lca});
	}

	sort(begin(t2), end(t2));
	t2.resize(unique(begin(t2), end(t2)) - begin(t2));

	ind = 1;
	dfs(t2, t2[0].second);

	for (auto [vl, i] : t2)
		Min[i][0] = Min[i][1] = inf;
	return Ans;
}

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