Submission #890097

#	Time	Username	Problem	Language	Result	Execution time	Memory
890097		Onown	Factories (JOI14_factories)	C++17	33 / 100	8018 ms	204368 KiB

factories

#include <bits/stdc++.h>
#include <factories.h>
#pragma  GCC optimize ("O2, unroll-loops")
#pragma  GCC optimize ("Ofast")
using namespace std;

const int N = 5e5 + 55, L = 2e0 + 20, Q = 185;
const long long I = 1e18 + 118;
int n, q, h[N], par[N][L];
long long ans, spt[N][L], dis[N];
vector<pair<int, int>> adj[N];

void dfs(int v, int p) {
	for (int i = 0; i < adj[v].size(); i++) {
		int u = adj[v][i].first, w = adj[v][i].second;
		if (u == p) {
			swap(adj[v].back(), adj[v][i]);
			adj[v].pop_back();
			if (i == adj[v].size())
				return;
			u = adj[v][i].first, w = adj[v][i].second;
		}

		par[u][0] = v;
		spt[u][0] = w;
		h[u] = h[v] + 1;
		dfs(u, v);
	}
}

void dfsu(int v, int p) {
	for (auto [u, w]: adj[v]) {
		dfsu(u, v);
		dis[v] = min(dis[v], dis[u] + w);
	}
}

void dfsd(int v, int p) {
	for (auto [u, w]: adj[v]) {
		dis[u] = min(dis[u], dis[v] + w);
		dfsd(u, v);
	}
}

long long distance(int v, int u) {
	long long res = 0;
	if (h[v] < h[u]) swap(v, u);
	for (int i = 0; i < L && res < ans; i++)
		if ((1 << i) & (h[v] - h[u])) {
			res += spt[v][i];
			v = par[v][i];
		}
	if (v == u) return res;

	for (int i = L - 1; i >= 0 && res < ans; i--)
		if (par[v][i] != par[u][i]) {
			res += spt[v][i] + spt[u][i];
			v = par[v][i];
			u = par[u][i];
		}
	return res + spt[v][0] + spt[u][0];
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for (int i = 0; i < n - 1; i++) {
		adj[A[i] + 1].push_back({B[i] + 1, D[i]});
		adj[B[i] + 1].push_back({A[i] + 1, D[i]});
	}

	dfs(1, 0);
	for (int i = 1; i < L; i++)
		for (int j = 1; j <= n; j++) {
			par[j][i] = par[par[j][i - 1]][i - 1];
			spt[j][i] = spt[j][i - 1] + spt[par[j][i - 1]][i - 1];
		}
}

long long Query(int S, int X[], int T, int Y[]) {
	ans = I;
	if (S < Q) {
		for (int i = 0; i < T; i++)
			for (int j = 0; j < S; j++)
				ans = min(ans, distance(Y[i] + 1, X[j] + 1));
		return ans;
	}
	
	for (int i = 0; i < N; dis[i++] = I);
	for (int i = 0; i < S; dis[X[i++] + 1] = 0); 
	dfsu(1, 0);
	dfsd(1, 0);

	for (int i = 0; i < T; i++)
		ans = min(ans, dis[Y[i] + 1]);
	return ans;
}

Compilation message (stderr)

factories.cpp:3:42: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    3 | #pragma  GCC optimize ("O2, unroll-loops")
      |                                          ^
factories.cpp:13:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   13 | void dfs(int v, int p) {
      |                      ^
factories.cpp: In function 'void dfs(int, int)':
factories.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for (int i = 0; i < adj[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
factories.cpp:19:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |    if (i == adj[v].size())
      |        ~~^~~~~~~~~~~~~~~~
factories.cpp: At global scope:
factories.cpp:31:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   31 | void dfsu(int v, int p) {
      |                       ^
factories.cpp:38:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   38 | void dfsd(int v, int p) {
      |                       ^
factories.cpp:45:32: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   45 | long long distance(int v, int u) {
      |                                ^
factories.cpp:64:43: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   64 | void Init(int N, int A[], int B[], int D[]) {
      |                                           ^
factories.cpp:79:47: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   79 | long long Query(int S, int X[], int T, int Y[]) {
      |                                               ^

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