Submission #792065

#	Time	Username	Problem	Language	Result	Execution time	Memory
792065		Blagoj	Factories (JOI14_factories)	C++17	100 / 100	3355 ms	178820 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;

#define ll long long

const ll MXN = 500005, INF = 1e18;

bool done[MXN];
int sz[MXN], cen[MXN], temp[MXN];
ll dist[MXN][20], ans[MXN];

vector<pair<int, ll>> g[MXN];

int getSize(int cur, int par = -1) {
	sz[cur] = 1;
	for (auto [next, cost] : g[cur]) {
		if (next != par && !done[next]) sz[cur] += getSize(next, cur);
	}
	return sz[cur];
}

int getCentroid(int cur, int des, int par = -1) {
	for (auto [next, cost] : g[cur]) {
		if (next != par && !done[next] && sz[next] > des / 2) return getCentroid(next, des, cur);
	}
	return cur;
}

void solve(int cur, int par, int top, ll dis) {
	dist[cur][temp[cur]++] = dis;
	for (auto [next, cost] : g[cur]) {
		if (next != par && !done[next]) {
			cen[next] = top;
			solve(next, cur, top, dis + cost);
		}
	}
}

void decomp(int cur) {
	cur = getCentroid(cur, getSize(cur));
	done[cur] = 1;
	solve(cur, cur, cur, 0);
	for (auto [next, cost] : g[cur]) {
		if (!done[next]) decomp(next);
	}
}

void update(int cur, int t = 1) {
	for (int Cur = cur, ind = temp[cur] - 1; Cur >= 0; Cur = cen[Cur], ind--) {
		if (t) ans[Cur] = min(ans[Cur], dist[cur][ind]);
		else ans[Cur] = INF;
	}
} 

ll query(int cur) {
	ll mn = INF;
	for (int Cur = cur, ind = temp[cur] - 1; Cur >= 0; Cur = cen[Cur], ind--) {
		mn = min(mn, ans[Cur] + dist[cur][ind]);
	}
	return mn;
}

void Init(int N, int A[], int B[], int D[]) {
	for (int i = 0; i < N; i++) {
		ans[i] = INF;
		cen[i] = -1;
		for (int j = 0; j < 20; j++) dist[i][j] = INF;
		if (i == N - 1) break;
		g[A[i]].push_back({B[i], D[i]});
		g[B[i]].push_back({A[i], D[i]});
	}
	decomp(0);
}

ll Query(int S, int X[], int T, int Y[]) { 
	for (int i = 0; i < S; i++) update(X[i]);
	ll mn = INF;
	for (int i = 0; i < T; i++) mn = min(mn, query(Y[i]));
	for (int i = 0; i < S; i++) update(X[i], 0);
	return mn;
}

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