# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
439839 |
2021-07-01T01:00:40 Z |
반딧불(#7618) |
도로 폐쇄 (APIO21_roads) |
C++17 |
|
2000 ms |
33084 KB |
#include <bits/stdc++.h>
#include "roads.h"
using namespace std;
typedef long long ll;
int n, k;
vector<pair<int, ll> > link[100002];
int deg[100002];
ll DP[100002][2];
int visited[100002];
vector<ll> ans;
void dfs(int x, int par = -1){
ll dp0Sum = 0;
vector<ll> diff (1, 0);
visited[x] = k;
for(auto y: link[x]){
if(deg[y.first] < k){
dp0Sum += y.second;
diff.push_back(y.second);
continue;
}
if(y.first == par) continue;
dfs(y.first, x);
DP[y.first][0] += y.second;
dp0Sum += DP[y.first][0];
diff.push_back(max(0LL, DP[y.first][0] - DP[y.first][1]));
}
sort(diff.rbegin(), diff.rend());
for(int i=1; i<(int)diff.size(); i++) diff[i] += diff[i-1];
DP[x][0] = dp0Sum - diff[min(k, (int)diff.size())-1];
DP[x][1] = dp0Sum - (k==1 ? 0 : diff[min(k-1, (int)diff.size())-1]);
}
vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
n = N;
ans.resize(n);
for(int i=0; i<n-1; i++){
link[U[i]].push_back(make_pair(V[i], W[i]));
link[V[i]].push_back(make_pair(U[i], W[i]));
ans[0] += W[i];
}
vector<pair<int, int> > degList;
for(int i=0; i<n; i++){
visited[i] = -1;
deg[i] = (int)link[i].size();
degList.push_back(make_pair(deg[i], i));
}
sort(degList.rbegin(), degList.rend());
for(int idx=1; idx<degList[0].first; idx++){
k = idx;
while(!degList.empty() && degList.back().first < idx) degList.pop_back();
if(degList.empty()) break;
// for(auto p: degList){
// vector<pair<int, ll> > tVec;
// for(auto p2: link[p.second]){
// if(deg[p2.first] < idx) continue;
// tVec.push_back(p2);
// }
// tVec.swap(link[p.second]);
// }
for(auto p: degList){
if(visited[p.second] != k){
dfs(p.second);
ans[idx] += DP[p.second][0];
}
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
160 ms |
2928 KB |
Output is correct |
3 |
Correct |
183 ms |
2924 KB |
Output is correct |
4 |
Correct |
61 ms |
2932 KB |
Output is correct |
5 |
Correct |
3 ms |
2636 KB |
Output is correct |
6 |
Correct |
3 ms |
2648 KB |
Output is correct |
7 |
Correct |
3 ms |
2648 KB |
Output is correct |
8 |
Correct |
63 ms |
2884 KB |
Output is correct |
9 |
Correct |
112 ms |
2892 KB |
Output is correct |
10 |
Correct |
3 ms |
2636 KB |
Output is correct |
11 |
Correct |
3 ms |
2636 KB |
Output is correct |
12 |
Execution timed out |
2080 ms |
10756 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
77 ms |
27788 KB |
Output is correct |
3 |
Correct |
85 ms |
30992 KB |
Output is correct |
4 |
Correct |
95 ms |
32940 KB |
Output is correct |
5 |
Correct |
94 ms |
33084 KB |
Output is correct |
6 |
Correct |
3 ms |
3148 KB |
Output is correct |
7 |
Correct |
4 ms |
3172 KB |
Output is correct |
8 |
Correct |
4 ms |
3148 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
56 ms |
20236 KB |
Output is correct |
13 |
Correct |
110 ms |
32084 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
77 ms |
29252 KB |
Output is correct |
16 |
Correct |
91 ms |
32128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
3 ms |
2644 KB |
Output is correct |
8 |
Correct |
3 ms |
2656 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
11 |
Correct |
3 ms |
2636 KB |
Output is correct |
12 |
Correct |
3 ms |
2636 KB |
Output is correct |
13 |
Correct |
3 ms |
2636 KB |
Output is correct |
14 |
Correct |
3 ms |
2636 KB |
Output is correct |
15 |
Correct |
3 ms |
2636 KB |
Output is correct |
16 |
Correct |
2 ms |
2644 KB |
Output is correct |
17 |
Correct |
2 ms |
2636 KB |
Output is correct |
18 |
Correct |
2 ms |
2636 KB |
Output is correct |
19 |
Correct |
3 ms |
2636 KB |
Output is correct |
20 |
Correct |
3 ms |
2636 KB |
Output is correct |
21 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
3 ms |
2644 KB |
Output is correct |
8 |
Correct |
3 ms |
2656 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
11 |
Correct |
3 ms |
2636 KB |
Output is correct |
12 |
Correct |
3 ms |
2636 KB |
Output is correct |
13 |
Correct |
3 ms |
2636 KB |
Output is correct |
14 |
Correct |
3 ms |
2636 KB |
Output is correct |
15 |
Correct |
3 ms |
2636 KB |
Output is correct |
16 |
Correct |
2 ms |
2644 KB |
Output is correct |
17 |
Correct |
2 ms |
2636 KB |
Output is correct |
18 |
Correct |
2 ms |
2636 KB |
Output is correct |
19 |
Correct |
3 ms |
2636 KB |
Output is correct |
20 |
Correct |
3 ms |
2636 KB |
Output is correct |
21 |
Correct |
2 ms |
2636 KB |
Output is correct |
22 |
Correct |
2 ms |
2648 KB |
Output is correct |
23 |
Correct |
3 ms |
2764 KB |
Output is correct |
24 |
Correct |
4 ms |
2892 KB |
Output is correct |
25 |
Correct |
4 ms |
2916 KB |
Output is correct |
26 |
Correct |
5 ms |
2892 KB |
Output is correct |
27 |
Correct |
26 ms |
2960 KB |
Output is correct |
28 |
Correct |
13 ms |
2892 KB |
Output is correct |
29 |
Correct |
4 ms |
2892 KB |
Output is correct |
30 |
Correct |
6 ms |
2892 KB |
Output is correct |
31 |
Correct |
6 ms |
2920 KB |
Output is correct |
32 |
Correct |
22 ms |
2892 KB |
Output is correct |
33 |
Correct |
4 ms |
3172 KB |
Output is correct |
34 |
Correct |
4 ms |
3148 KB |
Output is correct |
35 |
Correct |
4 ms |
3168 KB |
Output is correct |
36 |
Correct |
159 ms |
2916 KB |
Output is correct |
37 |
Correct |
180 ms |
2916 KB |
Output is correct |
38 |
Correct |
60 ms |
2928 KB |
Output is correct |
39 |
Correct |
2 ms |
2636 KB |
Output is correct |
40 |
Correct |
2 ms |
2636 KB |
Output is correct |
41 |
Correct |
2 ms |
2636 KB |
Output is correct |
42 |
Correct |
2 ms |
2636 KB |
Output is correct |
43 |
Correct |
2 ms |
2636 KB |
Output is correct |
44 |
Correct |
2 ms |
2636 KB |
Output is correct |
45 |
Correct |
2 ms |
2636 KB |
Output is correct |
46 |
Correct |
2 ms |
2636 KB |
Output is correct |
47 |
Correct |
2 ms |
2648 KB |
Output is correct |
48 |
Correct |
2 ms |
2636 KB |
Output is correct |
49 |
Correct |
3 ms |
2636 KB |
Output is correct |
50 |
Correct |
3 ms |
2636 KB |
Output is correct |
51 |
Correct |
3 ms |
2636 KB |
Output is correct |
52 |
Correct |
3 ms |
2636 KB |
Output is correct |
53 |
Correct |
5 ms |
2764 KB |
Output is correct |
54 |
Correct |
4 ms |
2892 KB |
Output is correct |
55 |
Correct |
23 ms |
2892 KB |
Output is correct |
56 |
Correct |
59 ms |
2884 KB |
Output is correct |
57 |
Correct |
94 ms |
2892 KB |
Output is correct |
58 |
Correct |
3 ms |
2636 KB |
Output is correct |
59 |
Correct |
2 ms |
2636 KB |
Output is correct |
60 |
Correct |
3 ms |
2636 KB |
Output is correct |
61 |
Correct |
3 ms |
2648 KB |
Output is correct |
62 |
Correct |
3 ms |
2636 KB |
Output is correct |
63 |
Correct |
2 ms |
2636 KB |
Output is correct |
64 |
Correct |
4 ms |
2924 KB |
Output is correct |
65 |
Correct |
5 ms |
2892 KB |
Output is correct |
66 |
Correct |
5 ms |
2892 KB |
Output is correct |
67 |
Correct |
22 ms |
2892 KB |
Output is correct |
68 |
Correct |
7 ms |
2948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
164 ms |
16064 KB |
Output is correct |
2 |
Correct |
171 ms |
15796 KB |
Output is correct |
3 |
Correct |
652 ms |
16828 KB |
Output is correct |
4 |
Correct |
245 ms |
16492 KB |
Output is correct |
5 |
Correct |
617 ms |
16844 KB |
Output is correct |
6 |
Execution timed out |
2076 ms |
15032 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
164 ms |
16064 KB |
Output is correct |
2 |
Correct |
171 ms |
15796 KB |
Output is correct |
3 |
Correct |
652 ms |
16828 KB |
Output is correct |
4 |
Correct |
245 ms |
16492 KB |
Output is correct |
5 |
Correct |
617 ms |
16844 KB |
Output is correct |
6 |
Execution timed out |
2076 ms |
15032 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
160 ms |
2928 KB |
Output is correct |
3 |
Correct |
183 ms |
2924 KB |
Output is correct |
4 |
Correct |
61 ms |
2932 KB |
Output is correct |
5 |
Correct |
3 ms |
2636 KB |
Output is correct |
6 |
Correct |
3 ms |
2648 KB |
Output is correct |
7 |
Correct |
3 ms |
2648 KB |
Output is correct |
8 |
Correct |
63 ms |
2884 KB |
Output is correct |
9 |
Correct |
112 ms |
2892 KB |
Output is correct |
10 |
Correct |
3 ms |
2636 KB |
Output is correct |
11 |
Correct |
3 ms |
2636 KB |
Output is correct |
12 |
Execution timed out |
2080 ms |
10756 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |