## Submission #446518

# Submission time Handle Problem Language Result Execution time Memory
446518 2021-07-22T09:31:21 Z Nima_Naderi Toll (APIO13_toll) C++14
16 / 100
8 ms 7372 KB
```//In the name of God
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
#define Mp make_pair
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<pair<ll, pll>, ll> kir;
const ll MXN = 3e5 + 10;
ll n, m, k;
ll A[MXN], from[MXN], to[MXN], W[MXN];
ll Par[MXN], Sz[MXN];
vector<pair<ll, pll>> E, E2;
ll Find(ll x){
return (Par[x] == x ? x : Par[x] = Find(Par[x]));
}
bool Union(ll x, ll y){
x = Find(x), y = Find(y);
if(x == y) return 0;
if(Sz[x] < Sz[y]) swap(x, y);
Par[y] = x, Sz[x] += Sz[y];
return 1;
}
inline void add_edge(ll u, ll v, ll w){
}
ll now;
void dfs(ll u, ll par, ll dis){
now += dis * A[u];
ll v, w; tie(v, w) = Pr;
if(v == par) continue;
dfs(v, u, dis + w);
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
cin >> n >> m >> k;
iota(Par, Par + n + 1, 0), fill(Sz, Sz + n + 1, 1);
for(int i = 1; i <= m; i ++){
ll u, v, w; cin >> u >> v >> w;
E.push_back(Mp(w, Mp(u, v)));
}
sort(E.begin(), E.end());
for(int i = 0; i < k; i ++){
ll u, v; cin >> u >> v;
from[i] = u, to[i] = v;
}
for(int i = 1; i <= n; i ++) cin >> A[i];
for(auto e : E){
ll w = e.first, u, v; tie(u, v) = e.second;
ll ru = Find(u), rv = Find(v);
if(ru == rv) continue;
if(ru > rv) swap(ru, rv);
for(int i = 0; i < k; i ++){
ll mu = Find(from[i]), mv = Find(to[i]);
if(mu > mv) swap(mu, mv);
if(mu == ru && mv == rv) W[i] = w;
}
Union(ru, rv);
}
ll ans = -1e18, base;
iota(Par, Par + n + 1, 0), fill(Sz, Sz + n + 1, 1);
for(int i = 1; i <= n; i ++) adj[i].clear();
E2.clear();
for(int i = 0; i < k; i ++){
E2.push_back(Mp(W[i], Mp(from[i], to[i])));
}
}
//sort(E2.begin(), E2.end());
vector<kir> E3;
for(auto e : E) E3.push_back(Mp(e, 0));
for(auto e : E2) E3.push_back(Mp(e, 1));
/*
for(auto e : E2){
ll w = e.first, u, v; tie(u, v) = e.second;
}
for(auto e : E){
ll w = e.first, u, v; tie(u, v) = e.second;
}
*/

sort(E3.begin(), E3.end());
for(auto ek : E3){
auto e = ek.first;
ll w = e.first, u, v; tie(u, v) = e.second;
if(Union(u, v)) add_edge(u, v, w * ek.second);
}

now = 0, dfs(1, 0, 0);
ans = max(ans, now);
}
cout << ans << '\n';
return 0;
}
// Nima
```

### Compilation message

```toll.cpp: In function 'int main()':
toll.cpp:65:18: warning: variable 'base' set but not used [-Wunused-but-set-variable]
65 |  ll ans = -1e18, base;
|                  ^~~~```

#### Subtask #1 16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7368 KB Output is correct

#### Subtask #2 0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7368 KB Output is correct
3 Incorrect 8 ms 7372 KB Output isn't correct
4 Halted 0 ms 0 KB -

#### Subtask #3 0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7368 KB Output is correct
3 Incorrect 8 ms 7372 KB Output isn't correct
4 Halted 0 ms 0 KB -

#### Subtask #4 0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7368 KB Output is correct
3 Incorrect 8 ms 7372 KB Output isn't correct
4 Halted 0 ms 0 KB -

#### Subtask #5 0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7368 KB Output is correct
3 Incorrect 8 ms 7372 KB Output isn't correct
4 Halted 0 ms 0 KB -