# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
439843 |
2021-07-01T01:32:06 Z |
반딧불(#7618) |
Road Closures (APIO21_roads) |
C++17 |
|
1061 ms |
416060 KB |
#include <bits/stdc++.h>
#include "roads.h"
using namespace std;
typedef long long ll;
struct Edge{
int u, v; ll w;
Edge(){}
Edge(int u, int v, ll w): u(u), v(v), w(w){}
};
struct segTree{
struct Node{
Node *l, *r;
ll s, e;
ll sum, cnt;
Node(ll s, ll e): s(s), e(e){
l = r = nullptr;
sum = cnt = 0;
}
~Node(){
if(l) delete l;
if(r) delete r;
}
void addValue(ll x, ll w){
if(s==e){
sum += x*w;
cnt += w;
return;
}
ll m = (s+e)>>1;
if(x <= m){
if(!l) l = new Node(s, m);
l->addValue(x, w);
}
else{
if(!r) r = new Node(m+1, e);
r->addValue(x, w);
}
sum = (l ? l->sum : 0LL) + (r ? r->sum : 0LL);
cnt = (l ? l->cnt : 0LL) + (r ? r->cnt : 0LL);
}
ll kthSum(ll k){
if(!k) return 0;
if(cnt <= k) return sum;
if(s==e) return k * s;
if(r && r->cnt >= k) return r->kthSum(k);
return (r ? r->sum : 0) + l->kthSum(k - (r?r->cnt:0));
}
} *root;
ll defVal;
segTree(){
root = new Node(0, 1e18);
defVal = 0;
}
void quit(){
if(root) delete root;
}
void addValue(ll x){
root->addValue(x, 1);
}
void delValue(ll x){
root->addValue(x, -1);
}
ll kthSum(ll k){
return defVal - root->kthSum(k);
}
} tree[100002];
int n, k;
vector<pair<int, ll> > link[100002];
vector<Edge> edgeList;
int deg[100002];
ll DP[100002][2];
int visited[100002];
vector<ll> ans;
void dfs(int x, int par = -1){
vector<pair<ll, ll> > vec;
visited[x] = k;
for(auto y: link[x]){
if(y.first == par) continue;
dfs(y.first, x);
vec.push_back(make_pair(DP[y.first][0] + y.second, DP[y.first][1]));
}
for(auto p: vec){
tree[x].defVal += p.first;
tree[x].addValue(max(p.first - p.second, 0LL));
}
DP[x][0] = tree[x].kthSum(k);
DP[x][1] = tree[x].kthSum(k-1);
for(auto p: vec){
tree[x].defVal -= p.first;
tree[x].delValue(p.first - p.second);
}
}
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++){
deg[U[i]]++, deg[V[i]]++;
edgeList.push_back(Edge(U[i], V[i], W[i]));
ans[0] += W[i];
}
vector<pair<int, int> > degList;
for(int i=0; i<n; i++){
visited[i] = -1;
degList.push_back(make_pair(deg[i], i));
}
sort(degList.rbegin(), degList.rend());
sort(edgeList.begin(), edgeList.end(), [&](Edge &a, Edge &b){
return min(deg[a.u], deg[a.v]) > min(deg[b.u], deg[b.v]);
});
for(int idx=1; idx<degList[0].first; idx++){
k = idx;
while(!degList.empty() && degList.back().first < idx){
int x = degList.back().second;
for(auto y: link[x]){
tree[y.first].defVal += y.second;
tree[y.first].addValue(y.second);
}
degList.pop_back();
}
if(degList.empty()) break;
while(!edgeList.empty()){
if(deg[edgeList.back().u] < idx || deg[edgeList.back().v] < idx) edgeList.pop_back();
else break;
}
for(auto p: degList) link[p.second].clear();
for(auto e: edgeList){
link[e.u].push_back(make_pair(e.v, e.w));
link[e.v].push_back(make_pair(e.u, e.w));
}
for(auto p: degList){
if(visited[p.second] != k){
dfs(p.second);
ans[idx] += DP[p.second][0];
}
}
}
for(int i=0; i<n; i++) tree[i].quit();
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
10444 KB |
Output is correct |
2 |
Correct |
18 ms |
13048 KB |
Output is correct |
3 |
Correct |
19 ms |
13132 KB |
Output is correct |
4 |
Correct |
12 ms |
10828 KB |
Output is correct |
5 |
Correct |
12 ms |
10700 KB |
Output is correct |
6 |
Correct |
13 ms |
10700 KB |
Output is correct |
7 |
Correct |
9 ms |
10444 KB |
Output is correct |
8 |
Correct |
15 ms |
10772 KB |
Output is correct |
9 |
Correct |
12 ms |
10700 KB |
Output is correct |
10 |
Correct |
9 ms |
10444 KB |
Output is correct |
11 |
Correct |
9 ms |
10444 KB |
Output is correct |
12 |
Correct |
144 ms |
19488 KB |
Output is correct |
13 |
Correct |
253 ms |
25968 KB |
Output is correct |
14 |
Correct |
727 ms |
98684 KB |
Output is correct |
15 |
Correct |
800 ms |
113772 KB |
Output is correct |
16 |
Correct |
788 ms |
111352 KB |
Output is correct |
17 |
Correct |
244 ms |
25976 KB |
Output is correct |
18 |
Correct |
9 ms |
10444 KB |
Output is correct |
19 |
Correct |
217 ms |
25416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
10444 KB |
Output is correct |
2 |
Correct |
703 ms |
346272 KB |
Output is correct |
3 |
Correct |
739 ms |
389260 KB |
Output is correct |
4 |
Correct |
879 ms |
415292 KB |
Output is correct |
5 |
Correct |
809 ms |
416060 KB |
Output is correct |
6 |
Correct |
24 ms |
17484 KB |
Output is correct |
7 |
Correct |
24 ms |
18532 KB |
Output is correct |
8 |
Correct |
22 ms |
17772 KB |
Output is correct |
9 |
Correct |
10 ms |
11084 KB |
Output is correct |
10 |
Correct |
10 ms |
11212 KB |
Output is correct |
11 |
Correct |
10 ms |
11212 KB |
Output is correct |
12 |
Correct |
464 ms |
253220 KB |
Output is correct |
13 |
Correct |
771 ms |
415520 KB |
Output is correct |
14 |
Correct |
9 ms |
10444 KB |
Output is correct |
15 |
Correct |
677 ms |
375696 KB |
Output is correct |
16 |
Correct |
759 ms |
415940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
10444 KB |
Output is correct |
2 |
Correct |
9 ms |
10396 KB |
Output is correct |
3 |
Correct |
8 ms |
10444 KB |
Output is correct |
4 |
Incorrect |
10 ms |
11212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
10444 KB |
Output is correct |
2 |
Correct |
9 ms |
10396 KB |
Output is correct |
3 |
Correct |
8 ms |
10444 KB |
Output is correct |
4 |
Incorrect |
10 ms |
11212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
999 ms |
253812 KB |
Output is correct |
2 |
Correct |
1020 ms |
249716 KB |
Output is correct |
3 |
Correct |
372 ms |
25092 KB |
Output is correct |
4 |
Correct |
1061 ms |
263584 KB |
Output is correct |
5 |
Correct |
350 ms |
25268 KB |
Output is correct |
6 |
Correct |
314 ms |
23208 KB |
Output is correct |
7 |
Correct |
692 ms |
164840 KB |
Output is correct |
8 |
Correct |
215 ms |
25632 KB |
Output is correct |
9 |
Correct |
736 ms |
203148 KB |
Output is correct |
10 |
Correct |
974 ms |
207292 KB |
Output is correct |
11 |
Correct |
365 ms |
25400 KB |
Output is correct |
12 |
Correct |
284 ms |
24884 KB |
Output is correct |
13 |
Correct |
9 ms |
10444 KB |
Output is correct |
14 |
Correct |
651 ms |
375784 KB |
Output is correct |
15 |
Correct |
753 ms |
415924 KB |
Output is correct |
16 |
Correct |
22 ms |
15436 KB |
Output is correct |
17 |
Correct |
23 ms |
15496 KB |
Output is correct |
18 |
Correct |
14 ms |
10956 KB |
Output is correct |
19 |
Correct |
14 ms |
10824 KB |
Output is correct |
20 |
Correct |
15 ms |
10916 KB |
Output is correct |
21 |
Correct |
233 ms |
25416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
999 ms |
253812 KB |
Output is correct |
2 |
Correct |
1020 ms |
249716 KB |
Output is correct |
3 |
Correct |
372 ms |
25092 KB |
Output is correct |
4 |
Correct |
1061 ms |
263584 KB |
Output is correct |
5 |
Correct |
350 ms |
25268 KB |
Output is correct |
6 |
Correct |
314 ms |
23208 KB |
Output is correct |
7 |
Correct |
692 ms |
164840 KB |
Output is correct |
8 |
Correct |
215 ms |
25632 KB |
Output is correct |
9 |
Correct |
736 ms |
203148 KB |
Output is correct |
10 |
Correct |
974 ms |
207292 KB |
Output is correct |
11 |
Correct |
365 ms |
25400 KB |
Output is correct |
12 |
Correct |
284 ms |
24884 KB |
Output is correct |
13 |
Correct |
9 ms |
10444 KB |
Output is correct |
14 |
Correct |
651 ms |
375784 KB |
Output is correct |
15 |
Correct |
753 ms |
415924 KB |
Output is correct |
16 |
Correct |
22 ms |
15436 KB |
Output is correct |
17 |
Correct |
23 ms |
15496 KB |
Output is correct |
18 |
Correct |
14 ms |
10956 KB |
Output is correct |
19 |
Correct |
14 ms |
10824 KB |
Output is correct |
20 |
Correct |
15 ms |
10916 KB |
Output is correct |
21 |
Correct |
233 ms |
25416 KB |
Output is correct |
22 |
Correct |
8 ms |
10444 KB |
Output is correct |
23 |
Correct |
11 ms |
10444 KB |
Output is correct |
24 |
Correct |
9 ms |
10492 KB |
Output is correct |
25 |
Incorrect |
1016 ms |
239820 KB |
Output isn't correct |
26 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
10444 KB |
Output is correct |
2 |
Correct |
18 ms |
13048 KB |
Output is correct |
3 |
Correct |
19 ms |
13132 KB |
Output is correct |
4 |
Correct |
12 ms |
10828 KB |
Output is correct |
5 |
Correct |
12 ms |
10700 KB |
Output is correct |
6 |
Correct |
13 ms |
10700 KB |
Output is correct |
7 |
Correct |
9 ms |
10444 KB |
Output is correct |
8 |
Correct |
15 ms |
10772 KB |
Output is correct |
9 |
Correct |
12 ms |
10700 KB |
Output is correct |
10 |
Correct |
9 ms |
10444 KB |
Output is correct |
11 |
Correct |
9 ms |
10444 KB |
Output is correct |
12 |
Correct |
144 ms |
19488 KB |
Output is correct |
13 |
Correct |
253 ms |
25968 KB |
Output is correct |
14 |
Correct |
727 ms |
98684 KB |
Output is correct |
15 |
Correct |
800 ms |
113772 KB |
Output is correct |
16 |
Correct |
788 ms |
111352 KB |
Output is correct |
17 |
Correct |
244 ms |
25976 KB |
Output is correct |
18 |
Correct |
9 ms |
10444 KB |
Output is correct |
19 |
Correct |
217 ms |
25416 KB |
Output is correct |
20 |
Correct |
8 ms |
10444 KB |
Output is correct |
21 |
Correct |
703 ms |
346272 KB |
Output is correct |
22 |
Correct |
739 ms |
389260 KB |
Output is correct |
23 |
Correct |
879 ms |
415292 KB |
Output is correct |
24 |
Correct |
809 ms |
416060 KB |
Output is correct |
25 |
Correct |
24 ms |
17484 KB |
Output is correct |
26 |
Correct |
24 ms |
18532 KB |
Output is correct |
27 |
Correct |
22 ms |
17772 KB |
Output is correct |
28 |
Correct |
10 ms |
11084 KB |
Output is correct |
29 |
Correct |
10 ms |
11212 KB |
Output is correct |
30 |
Correct |
10 ms |
11212 KB |
Output is correct |
31 |
Correct |
464 ms |
253220 KB |
Output is correct |
32 |
Correct |
771 ms |
415520 KB |
Output is correct |
33 |
Correct |
9 ms |
10444 KB |
Output is correct |
34 |
Correct |
677 ms |
375696 KB |
Output is correct |
35 |
Correct |
759 ms |
415940 KB |
Output is correct |
36 |
Correct |
8 ms |
10444 KB |
Output is correct |
37 |
Correct |
9 ms |
10396 KB |
Output is correct |
38 |
Correct |
8 ms |
10444 KB |
Output is correct |
39 |
Incorrect |
10 ms |
11212 KB |
Output isn't correct |
40 |
Halted |
0 ms |
0 KB |
- |