# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
439842 |
2021-07-01T01:28:55 Z |
반딧불(#7618) |
Road Closures (APIO21_roads) |
C++17 |
|
1048 ms |
417324 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(p.first - p.second);
}
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 |
13016 KB |
Output is correct |
3 |
Correct |
19 ms |
13132 KB |
Output is correct |
4 |
Correct |
13 ms |
10748 KB |
Output is correct |
5 |
Correct |
12 ms |
10700 KB |
Output is correct |
6 |
Correct |
13 ms |
10700 KB |
Output is correct |
7 |
Correct |
11 ms |
10444 KB |
Output is correct |
8 |
Correct |
13 ms |
10764 KB |
Output is correct |
9 |
Correct |
13 ms |
10800 KB |
Output is correct |
10 |
Correct |
9 ms |
10444 KB |
Output is correct |
11 |
Correct |
9 ms |
10480 KB |
Output is correct |
12 |
Correct |
145 ms |
19488 KB |
Output is correct |
13 |
Correct |
256 ms |
26980 KB |
Output is correct |
14 |
Correct |
722 ms |
100304 KB |
Output is correct |
15 |
Correct |
880 ms |
115428 KB |
Output is correct |
16 |
Correct |
781 ms |
113236 KB |
Output is correct |
17 |
Correct |
248 ms |
27848 KB |
Output is correct |
18 |
Correct |
8 ms |
10480 KB |
Output is correct |
19 |
Correct |
214 ms |
26224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
10444 KB |
Output is correct |
2 |
Incorrect |
658 ms |
346572 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
10444 KB |
Output is correct |
2 |
Correct |
9 ms |
10444 KB |
Output is correct |
3 |
Correct |
9 ms |
10444 KB |
Output is correct |
4 |
Incorrect |
10 ms |
11200 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
10444 KB |
Output is correct |
2 |
Correct |
9 ms |
10444 KB |
Output is correct |
3 |
Correct |
9 ms |
10444 KB |
Output is correct |
4 |
Incorrect |
10 ms |
11200 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1048 ms |
254008 KB |
Output is correct |
2 |
Correct |
1043 ms |
249712 KB |
Output is correct |
3 |
Correct |
358 ms |
25300 KB |
Output is correct |
4 |
Correct |
1041 ms |
263776 KB |
Output is correct |
5 |
Correct |
396 ms |
25192 KB |
Output is correct |
6 |
Correct |
329 ms |
23412 KB |
Output is correct |
7 |
Correct |
763 ms |
166200 KB |
Output is correct |
8 |
Correct |
219 ms |
26804 KB |
Output is correct |
9 |
Correct |
658 ms |
204284 KB |
Output is correct |
10 |
Correct |
891 ms |
208556 KB |
Output is correct |
11 |
Correct |
348 ms |
26856 KB |
Output is correct |
12 |
Correct |
269 ms |
26296 KB |
Output is correct |
13 |
Correct |
8 ms |
10444 KB |
Output is correct |
14 |
Correct |
691 ms |
377036 KB |
Output is correct |
15 |
Correct |
738 ms |
417324 KB |
Output is correct |
16 |
Correct |
22 ms |
15348 KB |
Output is correct |
17 |
Correct |
23 ms |
15400 KB |
Output is correct |
18 |
Correct |
18 ms |
11000 KB |
Output is correct |
19 |
Correct |
13 ms |
10724 KB |
Output is correct |
20 |
Correct |
15 ms |
10828 KB |
Output is correct |
21 |
Correct |
227 ms |
26292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1048 ms |
254008 KB |
Output is correct |
2 |
Correct |
1043 ms |
249712 KB |
Output is correct |
3 |
Correct |
358 ms |
25300 KB |
Output is correct |
4 |
Correct |
1041 ms |
263776 KB |
Output is correct |
5 |
Correct |
396 ms |
25192 KB |
Output is correct |
6 |
Correct |
329 ms |
23412 KB |
Output is correct |
7 |
Correct |
763 ms |
166200 KB |
Output is correct |
8 |
Correct |
219 ms |
26804 KB |
Output is correct |
9 |
Correct |
658 ms |
204284 KB |
Output is correct |
10 |
Correct |
891 ms |
208556 KB |
Output is correct |
11 |
Correct |
348 ms |
26856 KB |
Output is correct |
12 |
Correct |
269 ms |
26296 KB |
Output is correct |
13 |
Correct |
8 ms |
10444 KB |
Output is correct |
14 |
Correct |
691 ms |
377036 KB |
Output is correct |
15 |
Correct |
738 ms |
417324 KB |
Output is correct |
16 |
Correct |
22 ms |
15348 KB |
Output is correct |
17 |
Correct |
23 ms |
15400 KB |
Output is correct |
18 |
Correct |
18 ms |
11000 KB |
Output is correct |
19 |
Correct |
13 ms |
10724 KB |
Output is correct |
20 |
Correct |
15 ms |
10828 KB |
Output is correct |
21 |
Correct |
227 ms |
26292 KB |
Output is correct |
22 |
Correct |
9 ms |
10364 KB |
Output is correct |
23 |
Correct |
13 ms |
10448 KB |
Output is correct |
24 |
Correct |
9 ms |
10444 KB |
Output is correct |
25 |
Incorrect |
978 ms |
241836 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 |
13016 KB |
Output is correct |
3 |
Correct |
19 ms |
13132 KB |
Output is correct |
4 |
Correct |
13 ms |
10748 KB |
Output is correct |
5 |
Correct |
12 ms |
10700 KB |
Output is correct |
6 |
Correct |
13 ms |
10700 KB |
Output is correct |
7 |
Correct |
11 ms |
10444 KB |
Output is correct |
8 |
Correct |
13 ms |
10764 KB |
Output is correct |
9 |
Correct |
13 ms |
10800 KB |
Output is correct |
10 |
Correct |
9 ms |
10444 KB |
Output is correct |
11 |
Correct |
9 ms |
10480 KB |
Output is correct |
12 |
Correct |
145 ms |
19488 KB |
Output is correct |
13 |
Correct |
256 ms |
26980 KB |
Output is correct |
14 |
Correct |
722 ms |
100304 KB |
Output is correct |
15 |
Correct |
880 ms |
115428 KB |
Output is correct |
16 |
Correct |
781 ms |
113236 KB |
Output is correct |
17 |
Correct |
248 ms |
27848 KB |
Output is correct |
18 |
Correct |
8 ms |
10480 KB |
Output is correct |
19 |
Correct |
214 ms |
26224 KB |
Output is correct |
20 |
Correct |
8 ms |
10444 KB |
Output is correct |
21 |
Incorrect |
658 ms |
346572 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |