//oh god why
#include "roads.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
struct DS {
ll tot, dif, uval;
// least = best to edge
bool operator<(const DS& ot) const {
return dif > ot.dif;
}
};
vector<pl> pe;
vector<vector<ii> > g;
// vertex, edge color
vector<map<int,vector<DS>>> dpt;
vector<map<int,int> > degr;
vi wex;
void dfb(int u, int p, int col, int st, int deg) {
int kv = degr[u][col]-(1-st)-deg;
int sus = 0;
int kt = 0;
for(const auto& eg: dpt[u][col]) {
int v = eg.uval;
if(kt < kv && eg.dif > 0) {
dfb(v,u,col,0,deg);
sus++;
} else {
wex[v] |= deg;
dfb(v,u,col,1,deg);
}
kt++;
}
if(!st) {
sus++;
}
if(sus < kt+1) {
degr[u][col|deg] = degr[u][col]-sus;
}
if(sus > 0) {
degr[u][col] = degr[u][col]-deg;
}
}
void dfa(int u, int p, int deg) {
for(int i=0;i<g[u].size();i++) {
int v = g[u][i].first;
if(v == p) {continue;}
dfa(v,u,deg);
}
dpt[u][wex[u]];
for(const auto& colp: dpt[u]) {
int col = colp.first;
auto& subs = dpt[u][col];
sort(subs.begin(),subs.end());
pl res = {0,pe[u].second};
int kv = degr[u][col]-deg;
int kt = 0;
for(const auto& eg: subs) {
res.first += eg.tot;
res.second += eg.tot;
if(kt < kv) {
ll dv = max(eg.dif,0LL);
res.first += dv;
if(kt < kv-1) {
res.second += dv;
}
}
kt++;
}
if(u != p && col == wex[u]) {
dpt[p][col].push_back({res.first,res.second-res.first,u});
} else {
dfb(u,p,col,1,deg);
}
}
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
ll sus = 0;
pe.resize(N);
g.resize(N);
wex.resize(N);
int M = U.size();
for(int i=0;i<M;i++) {
int u = U[i];
int v = V[i];
int c = W[i];
g[u].emplace_back(v,c);
g[v].emplace_back(u,c);
sus += c;
}
int h = 0;
while(1<<h < N) {
h++;
}
vi ord;
{
stack<ii> st;
st.emplace(0,0);
ord.push_back(0);
while(!st.empty()) {
int u = st.top().first;
ord.push_back(u);
int p = st.top().second;
st.pop();
for(int i=0;i<g[u].size();i++) {
int v = g[u][i].first;
if(v == p) {continue;}
int c = g[u][i].second;
st.emplace(v,u);
pe[v] = {u,c};
}
}
}
degr.resize(N);
for(int i=0;i<N;i++) {
degr[i][0] = 1<<(h);
}
for(int db=h-1;db>=0;db--) {
dpt.assign(N,map<int,vector<DS>>());
dfa(0,0,1<<db);
}
vector<ll> ans(N);
for(int i=1;i<N;i++) {
ans[wex[i]+1] += pe[i].second;
}
for(int i=1;i<ans.size();i++) {
ans[i] += ans[i-1];
}
for(int i=0;i<ans.size();i++) {
ans[i] = sus-ans[i];
}
return ans;
}
Compilation message
roads.cpp: In function 'void dfa(int, int, int)':
roads.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i=0;i<g[u].size();i++) {
| ~^~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:116:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int i=0;i<g[u].size();i++) {
| ~^~~~~~~~~~~~
roads.cpp:137:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(int i=1;i<ans.size();i++) {
| ~^~~~~~~~~~~
roads.cpp:140:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for(int i=0;i<ans.size();i++) {
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
10 ms |
1708 KB |
Output is correct |
3 |
Correct |
9 ms |
1800 KB |
Output is correct |
4 |
Correct |
8 ms |
1712 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
6 ms |
1476 KB |
Output is correct |
9 |
Correct |
8 ms |
1704 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
825 ms |
50372 KB |
Output is correct |
13 |
Correct |
1570 ms |
85116 KB |
Output is correct |
14 |
Correct |
1690 ms |
76508 KB |
Output is correct |
15 |
Correct |
1938 ms |
85452 KB |
Output is correct |
16 |
Correct |
1866 ms |
86640 KB |
Output is correct |
17 |
Correct |
1345 ms |
86196 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1129 ms |
76612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
292 KB |
Output is correct |
2 |
Correct |
400 ms |
51384 KB |
Output is correct |
3 |
Correct |
545 ms |
57916 KB |
Output is correct |
4 |
Correct |
443 ms |
61820 KB |
Output is correct |
5 |
Correct |
470 ms |
61892 KB |
Output is correct |
6 |
Correct |
4 ms |
1356 KB |
Output is correct |
7 |
Correct |
4 ms |
1484 KB |
Output is correct |
8 |
Correct |
4 ms |
1356 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
249 ms |
36800 KB |
Output is correct |
13 |
Correct |
420 ms |
61108 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
432 ms |
55072 KB |
Output is correct |
16 |
Correct |
450 ms |
61040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1625 ms |
45828 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1625 ms |
45828 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
10 ms |
1708 KB |
Output is correct |
3 |
Correct |
9 ms |
1800 KB |
Output is correct |
4 |
Correct |
8 ms |
1712 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
6 ms |
1476 KB |
Output is correct |
9 |
Correct |
8 ms |
1704 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
825 ms |
50372 KB |
Output is correct |
13 |
Correct |
1570 ms |
85116 KB |
Output is correct |
14 |
Correct |
1690 ms |
76508 KB |
Output is correct |
15 |
Correct |
1938 ms |
85452 KB |
Output is correct |
16 |
Correct |
1866 ms |
86640 KB |
Output is correct |
17 |
Correct |
1345 ms |
86196 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1129 ms |
76612 KB |
Output is correct |
20 |
Correct |
0 ms |
292 KB |
Output is correct |
21 |
Correct |
400 ms |
51384 KB |
Output is correct |
22 |
Correct |
545 ms |
57916 KB |
Output is correct |
23 |
Correct |
443 ms |
61820 KB |
Output is correct |
24 |
Correct |
470 ms |
61892 KB |
Output is correct |
25 |
Correct |
4 ms |
1356 KB |
Output is correct |
26 |
Correct |
4 ms |
1484 KB |
Output is correct |
27 |
Correct |
4 ms |
1356 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
249 ms |
36800 KB |
Output is correct |
32 |
Correct |
420 ms |
61108 KB |
Output is correct |
33 |
Correct |
1 ms |
204 KB |
Output is correct |
34 |
Correct |
432 ms |
55072 KB |
Output is correct |
35 |
Correct |
450 ms |
61040 KB |
Output is correct |
36 |
Correct |
0 ms |
204 KB |
Output is correct |
37 |
Correct |
0 ms |
204 KB |
Output is correct |
38 |
Correct |
1 ms |
204 KB |
Output is correct |
39 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
40 |
Halted |
0 ms |
0 KB |
- |