oj.uz

Submission #564560

# Submission time Handle Problem Language Result Execution time Memory
564560 2022-05-19T11:04:36 Z hollwo_pelw Road Closures (APIO21_roads) C++17
5 / 100
 2000 ms 25468 KB 
#include "roads.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
 
multiset<long long> 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, long long 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<long long> 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];
	}

	for (auto v : add) upd(u, v, -1);
	for (auto v : del) upd(u, v, +1);
}
 
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 5 ms 7508 KB Output is correct
3 Correct 5 ms 7636 KB Output is correct
4 Correct 6 ms 7636 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 5 ms 7508 KB Output is correct
9 Correct 5 ms 7612 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 64 ms 14812 KB Output is correct
13 Correct 114 ms 19780 KB Output is correct
14 Correct 97 ms 18736 KB Output is correct
15 Correct 108 ms 19888 KB Output is correct
16 Correct 112 ms 20132 KB Output is correct
17 Correct 123 ms 20188 KB Output is correct
18 Correct 4 ms 7252 KB Output is correct
19 Correct 104 ms 18640 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7300 KB Output is correct
2 Execution timed out 2077 ms 25468 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Execution timed out 2090 ms 7252 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Execution timed out 2090 ms 7252 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2085 ms 17100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2085 ms 17100 KB Time limit exceeded
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 5 ms 7508 KB Output is correct
3 Correct 5 ms 7636 KB Output is correct
4 Correct 6 ms 7636 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 5 ms 7508 KB Output is correct
9 Correct 5 ms 7612 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 64 ms 14812 KB Output is correct
13 Correct 114 ms 19780 KB Output is correct
14 Correct 97 ms 18736 KB Output is correct
15 Correct 108 ms 19888 KB Output is correct
16 Correct 112 ms 20132 KB Output is correct
17 Correct 123 ms 20188 KB Output is correct
18 Correct 4 ms 7252 KB Output is correct
19 Correct 104 ms 18640 KB Output is correct
20 Correct 4 ms 7300 KB Output is correct
21 Execution timed out 2077 ms 25468 KB Time limit exceeded
22 Halted 0 ms 0 KB -