oj.uz

Submission #564542

# Submission time Handle Problem Language Result Execution time Memory
564542 2022-05-19T10:47:31 Z hollwo_pelw Road Closures (APIO21_roads) C++17
5 / 100
 129 ms 26644 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];
	}
}
 
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 7636 KB Output is correct
3 Correct 5 ms 7636 KB Output is correct
4 Correct 5 ms 7636 KB Output is correct
5 Correct 4 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 7508 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 56 ms 14844 KB Output is correct
13 Correct 91 ms 19860 KB Output is correct
14 Correct 87 ms 18728 KB Output is correct
15 Correct 105 ms 19892 KB Output is correct
16 Correct 112 ms 20068 KB Output is correct
17 Correct 105 ms 20148 KB Output is correct
18 Correct 3 ms 7252 KB Output is correct
19 Correct 80 ms 18704 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Incorrect 63 ms 26644 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 7252 KB Output is correct
2 Correct 4 ms 7252 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 7252 KB Output is correct
2 Correct 4 ms 7252 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 129 ms 20648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 129 ms 20648 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 5 ms 7636 KB Output is correct
3 Correct 5 ms 7636 KB Output is correct
4 Correct 5 ms 7636 KB Output is correct
5 Correct 4 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 7508 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 56 ms 14844 KB Output is correct
13 Correct 91 ms 19860 KB Output is correct
14 Correct 87 ms 18728 KB Output is correct
15 Correct 105 ms 19892 KB Output is correct
16 Correct 112 ms 20068 KB Output is correct
17 Correct 105 ms 20148 KB Output is correct
18 Correct 3 ms 7252 KB Output is correct
19 Correct 80 ms 18704 KB Output is correct
20 Correct 4 ms 7244 KB Output is correct
21 Incorrect 63 ms 26644 KB Output isn't correct
22 Halted 0 ms 0 KB -