## Submission #159297

# Submission time Handle Problem Language Result Execution time Memory
159297 2019-10-22T06:46:49 Z Dat160601 Toll (APIO13_toll) C++17
100 / 100
1824 ms 18736 KB
```#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second

typedef pair < int, pair <int, int> > Edge;

const int N = 1e5 + 7;

int n, m, k, u, v, w, a[N], pset[N], cnt = 0, num[N], dep[100];
long long ans = 0, f[100], dp[100], g[100];
vector <Edge> ed, tree, rem, tmp;
vector < pair <int, int> > kruskal[N], edge[100];

int fset(int x){
if(pset[x] == x) return x;
return pset[x] = fset(pset[x]);
}

bool unionset(int x, int y){
x = fset(x), y = fset(y);
if(x == y) return false;
pset[x] = y;
return true;
}

void dfs(int u, int par){
num[u] = cnt;
f[cnt] += a[u];
for(int i = 0; i < (int)kruskal[u].size(); i++){
int v = kruskal[u][i].fi;
if(v == par) continue;
dfs(v, u);
}
}

void redfs(int u, int par){
g[u] = f[u];
for(int i = 0; i < (int)edge[u].size(); i++){
int v = edge[u][i].fi;
if(v == par) continue;
pr[v] = mp(u, edge[u][i].se);
dep[v] = dep[u] + 1;
redfs(v, u);
g[u] += g[v];
}
}

int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> k;
for(int i = 1; i <= m; i++){
cin >> u >> v >> w;
ed.pb(mp(w, mp(u, v)));
}
for(int i = 1; i <= n; i++) pset[i] = i;
sort(ed.begin(), ed.end());
for(int i = 0; i < m; i++){
int u = ed[i].se.fi, v = ed[i].se.se;
if(unionset(u, v)){
tree.pb(ed[i]);
}
}
for(int i = 1; i <= n; i++) pset[i] = i;
for(int i = 1; i <= k; i++){
}
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 0; i < (int)tree.size(); i++){
int u = tree[i].se.fi, v = tree[i].se.se;
if(unionset(u, v)){
kruskal[u].pb(mp(v, tree[i].fi));
kruskal[v].pb(mp(u, tree[i].fi));
}
else rem.pb(tree[i]);
}
for(int i = 1; i <= n; i++){
if(!num[i]){
++cnt;
dfs(i, i);
}
}
for(int i = 1; i <= cnt; i++) pset[i] = i, dep[i] = 0, edge[i].clear();
bool ok = true;
long long res = 0;
for(int i = 0; i < k; i++){
dp[i + 1] = 1e9;
if(!(mask & (1 << i))) continue;
u = num[u], v = num[v];
if(!unionset(u, v)){
ok = false;
break;
}
edge[u].pb(mp(v, i + 1));
edge[v].pb(mp(u, i + 1));
}
if(!ok) continue;
tmp.clear();
for(Edge x : rem){
int u = num[x.se.fi], v = num[x.se.se];
if(!unionset(u, v)){
tmp.pb(x);
}
else edge[u].pb(mp(v, 0)), edge[v].pb(mp(u, 0));
}
redfs(num[1], num[1]);
for(Edge x : tmp){
int u = num[x.se.fi], v = num[x.se.se];
if(dep[u] > dep[v]) swap(u, v);
while(dep[u] < dep[v]){
if(pr[v].se != 0) dp[pr[v].se] = min(dp[pr[v].se], 1LL * x.fi);
v = pr[v].fi;
}
while(u != v){
if(pr[v].se != 0) dp[pr[v].se] = min(dp[pr[v].se], 1LL * x.fi);
if(pr[u].se != 0) dp[pr[u].se] = min(dp[pr[u].se], 1LL * x.fi);
v = pr[v].fi;
u = pr[u].fi;
}
}
for(int i = 0; i < k; i++){
if(!(mask & (1 << i))) continue;
u = num[u], v = num[v];
if(dep[u] > dep[v]) swap(u, v);
res += 1LL * dp[i + 1] * g[v];
}
ans = max(ans, res);
}
cout << ans;
}
```

#### Subtask #1 16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct

#### Subtask #2 18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct

#### Subtask #3 22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 7 ms 3064 KB Output is correct
6 Correct 7 ms 2936 KB Output is correct

#### Subtask #4 22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 7 ms 3064 KB Output is correct
6 Correct 7 ms 2936 KB Output is correct
7 Correct 250 ms 18620 KB Output is correct
8 Correct 255 ms 18704 KB Output is correct
9 Correct 262 ms 18700 KB Output is correct

#### Subtask #5 22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 7 ms 3064 KB Output is correct
6 Correct 7 ms 2936 KB Output is correct
7 Correct 250 ms 18620 KB Output is correct
8 Correct 255 ms 18704 KB Output is correct
9 Correct 262 ms 18700 KB Output is correct
10 Correct 1402 ms 18656 KB Output is correct
11 Correct 1791 ms 18648 KB Output is correct
12 Correct 1824 ms 18736 KB Output is correct