oj.uz

Submission #122612

# Submission time Handle Problem Language Result Execution time Memory
122612 2019-06-28T18:59:53 Z tinder Factories (JOI14_factories) C++14
100 / 100
 7446 ms 181652 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

#define v first
#define w second

const int maxn = 5e5 + 5;
using ll = long long;
using ii = pair<ll, ll>;

int N;
vector<ii> g[maxn], t[maxn];
int in[maxn], tym;
int lvl[maxn], dp[20][maxn];
ll dist[maxn];
ll f[maxn];

void dfs(int u, int p, ll dd) {
	if(p == -1) lvl[u] = 0;
	else lvl[u] = lvl[p] + 1;
	dist[u] = dd;

	dp[0][u] = p;
	for(int i = 1; i <= 18; i++) {
		int mid = dp[i - 1][u];
		if(mid != -1) dp[i][u] = dp[i - 1][mid];
		else break;
	}

	in[u] = tym++;

	for(ii e : g[u]) {
		if(e.v != p) {
			dfs(e.v, u, e.w + dd);
		}
	}
}

int __lca(int u, int v) {
	if(lvl[u] > lvl[v]) swap(u, v);
	int d = lvl[v] - lvl[u];
	for(int i = 0; i < 19; i++) {
		if(d & (1 << i)) {
			v = dp[i][v];
		}
	}
	if(u == v) return u;
	for(int i = 18; i >= 0; i--) {
		if(dp[i][u] != dp[i][v]) {
			u = dp[i][u];
			v = dp[i][v];
		}
	}
	return dp[0][u];
}

void Init(int _N, int A[], int B[], int D[]) {
	N = _N;
	for(int i = 0; i < N - 1; i++) {
		int u = A[i], v = B[i], w = D[i];
		g[u].emplace_back(v, w);
		g[v].emplace_back(u, w);
	}
	memset(dp, -1, sizeof dp);
	dfs(0, -1, 0LL);
}

long long Query(int S, int X[], int T, int Y[]) {
	// find nodes
	vector<int> all;
	for(int i = 0; i < S; i++) {
		all.emplace_back(X[i]);
	}
	for(int i = 0; i < T; i++) {
		all.emplace_back(Y[i]);
	}
	sort(all.begin(), all.end(), [](int x, int y){ return in[x] < in[y]; });
	all.erase(unique(all.begin(), all.end()), all.end());
	int sz = all.size();
	for(int i = 1; i < sz; i++) {
		all.emplace_back(__lca(all[i - 1], all[i]));
	}
	sort(all.begin(), all.end(), [](int x, int y){ return in[x] < in[y]; });
	all.erase(unique(all.begin(), all.end()), all.end());

	// clear
	for(int u : all) {
		t[u].clear();
		f[u] = 1e18;
	}

	// build tree
	for(int i = 1; i < all.size(); i++) {
		int u = __lca(all[i - 1], all[i]);
		int v = all[i];
		ll w = dist[v] - dist[u];
		t[u].emplace_back(ii(v, w));
		t[v].emplace_back(ii(u, w));
	}

	// Dijkstra
	priority_queue<ii, vector<ii>, greater<ii>> Q;
	for(int i = 0; i < S; i++) {
		f[X[i]] = 0;
		Q.emplace(0, X[i]);
	}
	while(Q.size()) {
		int u = Q.top().second;
		Q.pop();
		for(ii &e : t[u]) {
			if(f[e.v] > f[u] + e.w) {
				f[e.v] = f[u] + e.w;
				Q.emplace(f[e.v], e.v);
			}
		}
	}
	ll ans = 1e18;
	for(int i = 0; i < T; i++) {
		ans = min(ans, f[Y[i]]);
	}
	return ans;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:94:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < all.size(); i++) {
                 ~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 63484 KB Output is correct
2 Correct 1623 ms 81328 KB Output is correct
3 Correct 1861 ms 81276 KB Output is correct
4 Correct 1559 ms 81480 KB Output is correct
5 Correct 1223 ms 81400 KB Output is correct
6 Correct 1147 ms 81156 KB Output is correct
7 Correct 1773 ms 81284 KB Output is correct
8 Correct 1674 ms 81624 KB Output is correct
9 Correct 1229 ms 81400 KB Output is correct
10 Correct 1194 ms 81144 KB Output is correct
11 Correct 1770 ms 81160 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 63224 KB Output is correct
2 Correct 2554 ms 146668 KB Output is correct
3 Correct 3599 ms 147960 KB Output is correct
4 Correct 2069 ms 143804 KB Output is correct
5 Correct 2568 ms 172412 KB Output is correct
6 Correct 3749 ms 150460 KB Output is correct
7 Correct 2998 ms 99204 KB Output is correct
8 Correct 1505 ms 98808 KB Output is correct
9 Correct 1766 ms 103776 KB Output is correct
10 Correct 2876 ms 100600 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 63484 KB Output is correct
2 Correct 1623 ms 81328 KB Output is correct
3 Correct 1861 ms 81276 KB Output is correct
4 Correct 1559 ms 81480 KB Output is correct
5 Correct 1223 ms 81400 KB Output is correct
6 Correct 1147 ms 81156 KB Output is correct
7 Correct 1773 ms 81284 KB Output is correct
8 Correct 1674 ms 81624 KB Output is correct
9 Correct 1229 ms 81400 KB Output is correct
10 Correct 1194 ms 81144 KB Output is correct
11 Correct 1770 ms 81160 KB Output is correct
12 Correct 59 ms 63224 KB Output is correct
13 Correct 2554 ms 146668 KB Output is correct
14 Correct 3599 ms 147960 KB Output is correct
15 Correct 2069 ms 143804 KB Output is correct
16 Correct 2568 ms 172412 KB Output is correct
17 Correct 3749 ms 150460 KB Output is correct
18 Correct 2998 ms 99204 KB Output is correct
19 Correct 1505 ms 98808 KB Output is correct
20 Correct 1766 ms 103776 KB Output is correct
21 Correct 2876 ms 100600 KB Output is correct
22 Correct 6237 ms 163720 KB Output is correct
23 Correct 5737 ms 162836 KB Output is correct
24 Correct 7446 ms 166720 KB Output is correct
25 Correct 6764 ms 168384 KB Output is correct
26 Correct 6428 ms 159992 KB Output is correct
27 Correct 4513 ms 181652 KB Output is correct
28 Correct 3847 ms 158992 KB Output is correct
29 Correct 6260 ms 158808 KB Output is correct
30 Correct 6756 ms 158196 KB Output is correct
31 Correct 6564 ms 158748 KB Output is correct
32 Correct 2216 ms 105376 KB Output is correct
33 Correct 2000 ms 101972 KB Output is correct
34 Correct 2778 ms 98276 KB Output is correct
35 Correct 2798 ms 97912 KB Output is correct
36 Correct 3254 ms 98580 KB Output is correct
37 Correct 3198 ms 98444 KB Output is correct