oj.uz

Submission #564539

# Submission time Handle Problem Language Result Execution time Memory
564539 2022-05-19T10:45:30 Z hollwo_pelw Road Closures (APIO21_roads) C++17
5 / 100
 143 ms 28520 KB 
#include "roads.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;

multiset<int> st[MAXN];
long long sum[MAXN], dp[MAXN][2];
int deg[MAXN], vis[MAXN];
vector<pair<int, int>> adj[MAXN];

inline void upd(int u, int v, int op) {
	sum[u] += op * v;
	if (op == +1) 
		st[u].insert(v);
	if (op == -1) 
		st[u].erase(st[u].find(v));
}

void solve(int u) {
	vector<int> add, del;
	long long tot = 0;

	// need to del
	int X = vis[u], lim = deg[u] - X;

	while ((int)st[u].size() > lim)
		upd(u, *st[u].rbegin(), -1);

	for (auto [v, w] : adj[u]) {
		if (deg[v] <= X) break;
		if (vis[v] == X) continue;
		vis[v] = X;

		solve(v);
		tot += dp[v][0];

		add.push_back(dp[v][1] + w - dp[v][0]), upd(u, dp[v][1] + w - dp[v][0], +1);
	}

	for (int i = 0; i < 2; i++) {
		while ((int)st[u].size() > lim - i)
			del.push_back(*st[u].rbegin()), upd(u, *st[u].rbegin(), -1);
		dp[u][i] = tot + sum[u];
	}
}

vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
	for (int i = 0; i < N - 1; i++) {
		deg[U[i]] ++, deg[V[i]] ++;
		adj[U[i]].emplace_back(V[i], W[i]);
		adj[V[i]].emplace_back(U[i], W[i]);
	}
	for (int i = 0; i < N; i++)
		sort(adj[i].begin(), adj[i].end(), [&](const pair<int, int> &x, const pair<int, int> &y){ return deg[x.first] > deg[y.first]; });

	vector<long long> res(N);

	res[0] = accumulate(W.begin(), W.end(), 0ll);

	vector<int> p(N);
	iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&](const int &i, const int &j){
		return deg[i] < deg[j];
	});

	for (int X = 1, i = 0; X < N; X++) {
		for (; i < N && deg[p[i]] == X; i++) {
			for (auto [v, w] : adj[p[i]]) {
				if (deg[v] <= X) break;
				upd(v, w, 1);
			}
		}

		long long ans = 0;

		for (int j = i; j < N; j++)
			if (vis[p[j]] != X) {
				vis[p[j]] = X;
				solve(p[j]);
				ans += dp[p[j]][0];
			}

		res[X] = ans;
	}

	return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 6 ms 7636 KB Output is correct
3 Correct 5 ms 7624 KB Output is correct
4 Correct 7 ms 7580 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7400 KB Output is correct
7 Correct 6 ms 7356 KB Output is correct
8 Correct 5 ms 7508 KB Output is correct
9 Correct 6 ms 7624 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7292 KB Output is correct
12 Correct 63 ms 15428 KB Output is correct
13 Correct 114 ms 20800 KB Output is correct
14 Correct 98 ms 20304 KB Output is correct
15 Correct 121 ms 21668 KB Output is correct
16 Correct 119 ms 21832 KB Output is correct
17 Correct 109 ms 22032 KB Output is correct
18 Correct 4 ms 7252 KB Output is correct
19 Correct 90 ms 19536 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7352 KB Output is correct
2 Incorrect 68 ms 28520 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7352 KB Output is correct
2 Correct 4 ms 7308 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Incorrect 4 ms 7380 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7352 KB Output is correct
2 Correct 4 ms 7308 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Incorrect 4 ms 7380 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 143 ms 21948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 143 ms 21948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 6 ms 7636 KB Output is correct
3 Correct 5 ms 7624 KB Output is correct
4 Correct 7 ms 7580 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7400 KB Output is correct
7 Correct 6 ms 7356 KB Output is correct
8 Correct 5 ms 7508 KB Output is correct
9 Correct 6 ms 7624 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7292 KB Output is correct
12 Correct 63 ms 15428 KB Output is correct
13 Correct 114 ms 20800 KB Output is correct
14 Correct 98 ms 20304 KB Output is correct
15 Correct 121 ms 21668 KB Output is correct
16 Correct 119 ms 21832 KB Output is correct
17 Correct 109 ms 22032 KB Output is correct
18 Correct 4 ms 7252 KB Output is correct
19 Correct 90 ms 19536 KB Output is correct
20 Correct 5 ms 7352 KB Output is correct
21 Incorrect 68 ms 28520 KB Output isn't correct
22 Halted 0 ms 0 KB -