# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
533756 | 2022-03-07T07:04:08 Z | 1bin | 도로 폐쇄 (APIO21_roads) | C++14 | 209 ms | 87580 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]; ll dp[NMAX][2], S[NMAX]; vector<int> D[NMAX]; set<int> X; multiset<ll> A[NMAX], C[NMAX], t[NMAX]; void dfs(int now, int k) { vis[now] = 1; ll& ret = dp[now][0] = 0; vector<ll> tmp; ll c = 0; 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++; tmp.emplace_back(t); } while (t[now].size() && A[now].size() < k - c) { auto it = t[now].begin(); A[now].emplace(*it); S[now] += *it; t[now].erase(it); } while (A[now].size() && A[now].size() > k - c) { auto it = --A[now].end(); S[now] -= *it; t[now].emplace(*it); A[now].erase(it); } ret += S[now]; /*cout << "now is : " << now << ' ' << ret << '\n'; for (ll x : A[now]) cout << x << ' '; cout << '\n'; for (ll x : C[now]) cout << x << ' '; cout << '\n';*/ for (ll x : tmp) C[now].emplace(x); auto it = t[now].begin(); for (int i = 0; i < c && t[now].size(); i++) C[now].emplace(*it++); if (!c) { //cout << k << ' ' << now << ' ' << ret << '\n'; //cout << ret << '\n'; dp[now][1] = ret - *A[now].rbegin(); return; } it = C[now].begin(); int sz = k - 1 - A[now].size(); if (sz < 0 && c >= k) assert(0); while(sz--) ret += min(*it++, 0LL); dp[now][1] = ret; ret += min(*it, 0LL); //cout << ret << '\n'; //cout << "Now is : " << now << '\n'; //for(ll x : C[now]) cout << x << ' '; //cout << '\n'; C[now].clear(); 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 }); S[nx] += w; t[nx].emplace(-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; } /* 5 0 1 1 0 2 4 0 3 3 2 4 2 */ /* 4 0 1 5 0 3 5 0 2 10 */ /* 5 0 1 5 1 2 6 2 3 1 3 4 8 */ /* 5 0 1 1 0 2 2 0 3 3 0 4 4 */ //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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 21324 KB | Output is correct |
2 | Correct | 13 ms | 21764 KB | Output is correct |
3 | Correct | 13 ms | 21836 KB | Output is correct |
4 | Correct | 14 ms | 21880 KB | Output is correct |
5 | Correct | 11 ms | 21360 KB | Output is correct |
6 | Correct | 11 ms | 21452 KB | Output is correct |
7 | Correct | 11 ms | 21452 KB | Output is correct |
8 | Correct | 13 ms | 21824 KB | Output is correct |
9 | Correct | 12 ms | 21880 KB | Output is correct |
10 | Correct | 12 ms | 21376 KB | Output is correct |
11 | Correct | 11 ms | 21452 KB | Output is correct |
12 | Correct | 113 ms | 34172 KB | Output is correct |
13 | Correct | 199 ms | 42556 KB | Output is correct |
14 | Correct | 184 ms | 40448 KB | Output is correct |
15 | Correct | 204 ms | 42536 KB | Output is correct |
16 | Correct | 209 ms | 42824 KB | Output is correct |
17 | Correct | 209 ms | 42808 KB | Output is correct |
18 | Correct | 11 ms | 21324 KB | Output is correct |
19 | Correct | 190 ms | 40664 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 21352 KB | Output is correct |
2 | Correct | 97 ms | 55552 KB | Output is correct |
3 | Correct | 110 ms | 59896 KB | Output is correct |
4 | Correct | 112 ms | 62436 KB | Output is correct |
5 | Correct | 120 ms | 62396 KB | Output is correct |
6 | Correct | 12 ms | 22092 KB | Output is correct |
7 | Correct | 17 ms | 22176 KB | Output is correct |
8 | Correct | 12 ms | 22168 KB | Output is correct |
9 | Correct | 13 ms | 21452 KB | Output is correct |
10 | Correct | 13 ms | 21516 KB | Output is correct |
11 | Correct | 12 ms | 21484 KB | Output is correct |
12 | Correct | 67 ms | 46044 KB | Output is correct |
13 | Correct | 107 ms | 62428 KB | Output is correct |
14 | Correct | 17 ms | 21364 KB | Output is correct |
15 | Correct | 98 ms | 58356 KB | Output is correct |
16 | Correct | 108 ms | 62416 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 21324 KB | Output is correct |
2 | Correct | 11 ms | 21452 KB | Output is correct |
3 | Correct | 11 ms | 21452 KB | Output is correct |
4 | Runtime error | 27 ms | 43320 KB | Execution killed with signal 6 |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 21324 KB | Output is correct |
2 | Correct | 11 ms | 21452 KB | Output is correct |
3 | Correct | 11 ms | 21452 KB | Output is correct |
4 | Runtime error | 27 ms | 43320 KB | Execution killed with signal 6 |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 135 ms | 87580 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 135 ms | 87580 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 21324 KB | Output is correct |
2 | Correct | 13 ms | 21764 KB | Output is correct |
3 | Correct | 13 ms | 21836 KB | Output is correct |
4 | Correct | 14 ms | 21880 KB | Output is correct |
5 | Correct | 11 ms | 21360 KB | Output is correct |
6 | Correct | 11 ms | 21452 KB | Output is correct |
7 | Correct | 11 ms | 21452 KB | Output is correct |
8 | Correct | 13 ms | 21824 KB | Output is correct |
9 | Correct | 12 ms | 21880 KB | Output is correct |
10 | Correct | 12 ms | 21376 KB | Output is correct |
11 | Correct | 11 ms | 21452 KB | Output is correct |
12 | Correct | 113 ms | 34172 KB | Output is correct |
13 | Correct | 199 ms | 42556 KB | Output is correct |
14 | Correct | 184 ms | 40448 KB | Output is correct |
15 | Correct | 204 ms | 42536 KB | Output is correct |
16 | Correct | 209 ms | 42824 KB | Output is correct |
17 | Correct | 209 ms | 42808 KB | Output is correct |
18 | Correct | 11 ms | 21324 KB | Output is correct |
19 | Correct | 190 ms | 40664 KB | Output is correct |
20 | Correct | 12 ms | 21352 KB | Output is correct |
21 | Correct | 97 ms | 55552 KB | Output is correct |
22 | Correct | 110 ms | 59896 KB | Output is correct |
23 | Correct | 112 ms | 62436 KB | Output is correct |
24 | Correct | 120 ms | 62396 KB | Output is correct |
25 | Correct | 12 ms | 22092 KB | Output is correct |
26 | Correct | 17 ms | 22176 KB | Output is correct |
27 | Correct | 12 ms | 22168 KB | Output is correct |
28 | Correct | 13 ms | 21452 KB | Output is correct |
29 | Correct | 13 ms | 21516 KB | Output is correct |
30 | Correct | 12 ms | 21484 KB | Output is correct |
31 | Correct | 67 ms | 46044 KB | Output is correct |
32 | Correct | 107 ms | 62428 KB | Output is correct |
33 | Correct | 17 ms | 21364 KB | Output is correct |
34 | Correct | 98 ms | 58356 KB | Output is correct |
35 | Correct | 108 ms | 62416 KB | Output is correct |
36 | Correct | 11 ms | 21324 KB | Output is correct |
37 | Correct | 11 ms | 21452 KB | Output is correct |
38 | Correct | 11 ms | 21452 KB | Output is correct |
39 | Runtime error | 27 ms | 43320 KB | Execution killed with signal 6 |
40 | Halted | 0 ms | 0 KB | - |