oj.uz

Submission #142652

# Submission time Handle Problem Language Result Execution time Memory
142652 2019-08-10T09:19:56 Z RafaelSus Transport (COCI19_transport) C++14
130 / 130
 490 ms 20888 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
const int maxn = 1e5 + 5;
const int inf = 1000 * 1000 * 1000;

int n, a[maxn], w[maxn];
vector <pair<int, long long>> g[maxn];
int used[maxn];
int con;

long long dp1[maxn], ben1[maxn];
long long dp2[maxn], ben2[maxn];
int sz[maxn];
long long answ;

void sizeCounter(int v, int p) {
	++con;
	sz[v] = 1;
	dp1[v] = dp2[v] = 0;
	ben1[v] = ben2[v] = 0;
	for (size_t i = 0; i < g[v].size(); i++) {
		int to = g[v][i].first;
		if (to == p || used[to]) continue;
		sizeCounter(to, v);
		sz[v] += sz[to];
	}
}


int center = 0;
int m;

void dfs(int v, int p) {
	int mx = con - sz[v];
	for (int i = 0; i < (int)g[v].size(); i++) {
		int to = g[v][i].first;
		int len = g[v][i].second;
		if (to == p || used[to])continue;
		dfs(to, v);
		mx = max(mx, sz[to]);
	}
	if (mx < m) {
		m = mx;
		center = v;
	}
}

vector <long long> G;

void push_DP(int v, int p) {
	sz[v] = 1;
	for (size_t i = 0; i < g[v].size(); i++) {
		int to = g[v][i].first;
		int len = g[v][i].second;
		if (to == p || used[to]) continue;

		ben1[to] = ben1[v] + a[v] - len;
		dp1[to] = dp1[v];
		if (ben1[to] < 0) {
			dp1[to] -= ben1[to];
			ben1[to] = 0;
		}

		int d = a[to] - len;
		dp2[to] = dp2[v] + d;
		ben2[to] = min(1ll * d, ben2[v] + d);

		push_DP(to, v);
		sz[v] += sz[to];
	}

	if (ben2[v] >= 0) {
		G.push_back(dp2[v]);
	}
}

int findCenter(int v) {
	con = 0;
	sizeCounter(v, -1);
	center = v;
	m = inf;
	dfs(v, -1);
	push_DP(center, -1);
	return center;
}


vector <long long> P;
vector <int> ver;

void solve(int v, int p) {

	if (p != -1) {
		ver.push_back(v);
		if (ben2[v] >= 0) {
			P.push_back(dp2[v]);
		}
	}

	int idx = lower_bound(G.begin(), G.end(), dp1[v]) - G.begin();
	answ += (int)G.size() - idx;
	if (p == -1) answ--;

	for (size_t i = 0; i < g[v].size(); i++) {
		int to = g[v][i].first;
		if (to == p || used[to]) continue;
		solve(to, v);
		if (p == -1) {
			sort(P.begin(), P.end());
			for (size_t j = 0; j < ver.size(); j++) {
				int u = ver[j];
				int id = lower_bound(P.begin(), P.end(), dp1[u]) - P.begin();
				answ -= (int)P.size() - id;
			}
			P.clear();
			ver.clear();
		}
	}
}

void centroidDecomposition() {
	queue <int> q;
	q.push(1);
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		v = findCenter(v);
		sort(G.begin(), G.end());
		solve(v, -1);
		G.clear();

		for (size_t i = 0; i < g[v].size(); i++) {
			int to = g[v][i].first;
			if (used[to] || sz[to] == 1) continue;
			q.push(to);
		}
		used[v] = 1;
	}
}


int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (size_t i = 1; i <= n; i++)
		cin >> a[i];
	for (size_t i = 0; i < n - 1; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		g[x].push_back({ y, z });
		g[y].push_back({ x, z });
	}

	centroidDecomposition();
	printf("%lld\n", answ);
	return 0;
}

Compilation message

transport.cpp: In function 'void dfs(int, int)':
transport.cpp:41:7: warning: unused variable 'len' [-Wunused-variable]
   int len = g[v][i].second;
       ^~~
transport.cpp: In function 'int main()':
transport.cpp:152:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (size_t i = 1; i <= n; i++)
                     ~~^~~~
transport.cpp:154:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (size_t i = 0; i < n - 1; i++) {
                     ~~^~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3064 KB Output is correct
2 Correct 9 ms 3192 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3416 KB Output is correct
2 Correct 12 ms 3448 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 9828 KB Output is correct
2 Correct 76 ms 9848 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 12280 KB Output is correct
2 Correct 134 ms 14836 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 15736 KB Output is correct
2 Correct 209 ms 20888 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 5696 KB Output is correct
2 Correct 44 ms 4984 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 7388 KB Output is correct
2 Correct 161 ms 6996 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 9116 KB Output is correct
2 Correct 233 ms 9080 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 10696 KB Output is correct
2 Correct 339 ms 10712 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 13388 KB Output is correct
2 Correct 430 ms 14332 KB Output is correct