oj.uz

답안 #533728

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
533728 2022-03-07T04:47:09 Z 1bin 도로 폐쇄 (APIO21_roads) C++14
5 / 100
 242 ms 85568 KB 
#include <bits/stdc++.h>
#include <cassert>

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], e[NMAX];
ll dp[NMAX][2], Sum[NMAX];
vector<int> D[NMAX];
set<int> X;
multiset<ll> C[NMAX], L[NMAX], R[NMAX];

/*
5
0 1 1
0 2 4
0 3 3
2 4 2
*/

/*
4
0 1 5
0 3 5
0 2 10
*/
void dfs(int now, int k) {
	vis[now] = 1;

	while (e[now] - dg[now] > L[now].size()) {
		assert(R[now].size());
		auto it = R[now].begin();
		//cout << "put : " << now << ' ' << *it << '\n';
		L[now].emplace(*it);  Sum[now] += *it;
		R[now].erase(it);
	}
	while (e[now] - dg[now] < L[now].size()) {
		assert(L[now].size());
		auto it = --L[now].end(); Sum[now] -= *it;
		//cout << "unput : " << now << ' ' << *it << '\n';
		R[now].emplace(*it);
		L[now].erase(it);
	}
	ll& ret = dp[now][0] = Sum[now];

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

	
	//cout << "node is : " << now << ' ' << e[now] << ' ' << Sum[now] << '\n';
	
	// dp[now][0]
	auto it = R[now].begin();
	for (int i = 0; i < dg[now] && it != R[now].end(); i++) C[now].emplace(*it++);
	it = C[now].begin();
	/*for (ll x : L[now]) cout << x << ' ';
	cout << '\n';
	for (ll x : R[now]) cout << x << ' ';
	cout << '\n';
	for (ll x : C[now]) cout << x << ' ';
	cout << '\n';*/

	for(int i= 0; i < dg[now]; i++) /*assert(it != C[now].end()),*/ret += *it++;
	//cout << "ans + " << ret << "\n\n";

	// dp[now][1]
	ll p;
	//assert(C[now].size() || R[now].size());
	if (C[now].size()) p = *C[now].begin();
	else p = *R[now].begin();
	dp[now][1] = ret + p;

	C[now].clear();
	e[now]--;
	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); e[i] = dg[i] - 1;
		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[nx]--;
				R[nx].emplace(w);
				if (L[nx].size()) {
					auto l = --L[nx].end();
					auto r = R[nx].begin();
					ll lv = *l, rv = *r;
					if (lv > rv) {
						L[nx].erase(l); L[nx].emplace(rv);
						R[nx].erase(r); R[nx].emplace(lv);
					}
				}
			}
		}

		// 각 트리에 대해서 탐색
		for (int x : X) if (!vis[x]) {
			dfs(x, k);
			ans[k] += dp[x][0];
			//cout << "ans :  " << dp[x][0] << '\n';
		}
		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;
//}

Compilation message

roads.cpp: In function 'void dfs(int, int)':
roads.cpp:33:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  while (e[now] - dg[now] > L[now].size()) {
      |         ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
roads.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  while (e[now] - dg[now] < L[now].size()) {
      |         ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 21324 KB Output is correct
2 Correct 12 ms 21812 KB Output is correct
3 Correct 14 ms 21836 KB Output is correct
4 Correct 12 ms 21836 KB Output is correct
5 Correct 10 ms 21484 KB Output is correct
6 Correct 10 ms 21452 KB Output is correct
7 Correct 11 ms 21456 KB Output is correct
8 Correct 12 ms 21712 KB Output is correct
9 Correct 13 ms 21788 KB Output is correct
10 Correct 11 ms 21452 KB Output is correct
11 Correct 13 ms 21456 KB Output is correct
12 Correct 144 ms 34432 KB Output is correct
13 Correct 229 ms 42852 KB Output is correct
14 Correct 193 ms 40804 KB Output is correct
15 Correct 236 ms 42864 KB Output is correct
16 Correct 239 ms 43172 KB Output is correct
17 Correct 242 ms 43180 KB Output is correct
18 Correct 11 ms 21324 KB Output is correct
19 Correct 203 ms 40800 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 21324 KB Output is correct
2 Runtime error 92 ms 79540 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 21324 KB Output is correct
2 Correct 12 ms 21452 KB Output is correct
3 Correct 11 ms 21452 KB Output is correct
4 Runtime error 26 ms 43404 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 21324 KB Output is correct
2 Correct 12 ms 21452 KB Output is correct
3 Correct 11 ms 21452 KB Output is correct
4 Runtime error 26 ms 43404 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 135 ms 85568 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 135 ms 85568 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 21324 KB Output is correct
2 Correct 12 ms 21812 KB Output is correct
3 Correct 14 ms 21836 KB Output is correct
4 Correct 12 ms 21836 KB Output is correct
5 Correct 10 ms 21484 KB Output is correct
6 Correct 10 ms 21452 KB Output is correct
7 Correct 11 ms 21456 KB Output is correct
8 Correct 12 ms 21712 KB Output is correct
9 Correct 13 ms 21788 KB Output is correct
10 Correct 11 ms 21452 KB Output is correct
11 Correct 13 ms 21456 KB Output is correct
12 Correct 144 ms 34432 KB Output is correct
13 Correct 229 ms 42852 KB Output is correct
14 Correct 193 ms 40804 KB Output is correct
15 Correct 236 ms 42864 KB Output is correct
16 Correct 239 ms 43172 KB Output is correct
17 Correct 242 ms 43180 KB Output is correct
18 Correct 11 ms 21324 KB Output is correct
19 Correct 203 ms 40800 KB Output is correct
20 Correct 12 ms 21324 KB Output is correct
21 Runtime error 92 ms 79540 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -