oj.uz

Submission #533585

# Submission time Handle Problem Language Result Execution time Memory
533585 2022-03-06T11:14:06 Z 1bin Road Closures (APIO21_roads) C++14
0 / 100
 2000 ms 47932 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
set<pair<ll, ll>> adj[NMAX];
int dg[NMAX], vis[NMAX];
ll dp[NMAX][2], S[NMAX];
vector<int> D[NMAX];
set<int> X;
multiset<ll> C[NMAX];

void dfs(int now, int k) {
	vis[now] = 1;
	ll& ret = dp[now][0] = S[now];

	vector<ll> tmp;
	for(auto& p : adj[now]) {
		ll nx = p.first, w = p.second;
		if(vis[nx]) continue;
		dfs(nx, k);
		ret += dp[nx][0] + w;
		ll t = dp[nx][1] - dp[nx][0] - w;
		C[now].emplace(t);
		tmp.emplace_back(t);
	}

	auto it = C[now].begin();
	for(int i = 0; i < k - 1; i++) ret += *it++;
	dp[now][1] = ret;
	ret += *it;

	//cout << "Now is : " << now << '\n';
	//for(ll x : C[now]) cout << x << ' ';
	//cout << '\n';
	for(ll t : tmp) C[now].erase(C[now].find(t));
	return;
}

vector<ll> minimum_closure_costs (int N, vector<int> U, vector<int> V, vector<int> W) {
	vector<ll> ans(N, 0);
	for(int i = 0; i < N - 1; i++) {
		adj[U[i]].emplace(V[i], W[i]);
		adj[V[i]].emplace(U[i], W[i]);
		dg[U[i]]++; dg[V[i]]++;
		ans[0] += W[i];
	}
	for(int i = 0; i < N; i++) {
		D[dg[i]].emplace_back(i);
		X.emplace(i);
	}

	for(int k = 1; k < N; k++) {
		// 노드 삭제하기
		//cout << "NOW TURN IS : " << k << '\n';
		for(int x : D[k]) {
			X.erase(x);
			//cout << "erase : " << x << '\n';
			for(auto& p : adj[x]) {
				ll nx = p.first, w = p.second;
				adj[nx].erase({ x, w });
				dg[x]--; dg[nx]--;
				C[nx].emplace(-w); S[nx] += w;
			}
		}
		
		// 각 트리에 대해서 탐색
		for(int x : X) if(!vis[x]) {
			dfs(x, k);
			ans[k] += dp[x][0];
		}
		for(int x : X) vis[x] = 0;
	}
	return ans;
}
//
//int main(void) {
//	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//
//	freopen("input.txt", "r", stdin);
//	int N;
//	cin >> N;
//	vector<int> U(N), V(N), W(N);
//	for(int i = 0; i < N - 1; i++) cin >> U[i] >> V[i] >> W[i];
//	vector<ll> ans = minimum_closure_costs(N, U, V, W);
//	for(int i = 0; i < N; i++) cout << ans[i] << ' ';
//	return 0;
//}#include "roads.h"

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12044 KB Output is correct
2 Correct 25 ms 12492 KB Output is correct
3 Correct 25 ms 12508 KB Output is correct
4 Correct 18 ms 12456 KB Output is correct
5 Correct 6 ms 12088 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 12108 KB Output is correct
8 Correct 17 ms 12364 KB Output is correct
9 Correct 26 ms 12492 KB Output is correct
10 Correct 7 ms 12048 KB Output is correct
11 Correct 8 ms 12052 KB Output is correct
12 Execution timed out 2072 ms 25308 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12044 KB Output is correct
2 Incorrect 96 ms 47932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 7 ms 11980 KB Output is correct
3 Correct 8 ms 11980 KB Output is correct
4 Incorrect 6 ms 11980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 7 ms 11980 KB Output is correct
3 Correct 8 ms 11980 KB Output is correct
4 Incorrect 6 ms 11980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 36688 KB Output is correct
2 Correct 228 ms 36236 KB Output is correct
3 Correct 614 ms 36412 KB Output is correct
4 Correct 233 ms 37340 KB Output is correct
5 Correct 591 ms 36444 KB Output is correct
6 Correct 1931 ms 35064 KB Output is correct
7 Correct 405 ms 37284 KB Output is correct
8 Execution timed out 2051 ms 32948 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 36688 KB Output is correct
2 Correct 228 ms 36236 KB Output is correct
3 Correct 614 ms 36412 KB Output is correct
4 Correct 233 ms 37340 KB Output is correct
5 Correct 591 ms 36444 KB Output is correct
6 Correct 1931 ms 35064 KB Output is correct
7 Correct 405 ms 37284 KB Output is correct
8 Execution timed out 2051 ms 32948 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12044 KB Output is correct
2 Correct 25 ms 12492 KB Output is correct
3 Correct 25 ms 12508 KB Output is correct
4 Correct 18 ms 12456 KB Output is correct
5 Correct 6 ms 12088 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 12108 KB Output is correct
8 Correct 17 ms 12364 KB Output is correct
9 Correct 26 ms 12492 KB Output is correct
10 Correct 7 ms 12048 KB Output is correct
11 Correct 8 ms 12052 KB Output is correct
12 Execution timed out 2072 ms 25308 KB Time limit exceeded
13 Halted 0 ms 0 KB -