| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 860709 |
2023-10-13T22:48:08 Z |
beaboss |
Toll (APIO13_toll) |
C++14 |
|
1 ms |
1116 KB |
// Source: https://oj.uz/problem/view/APIO13_toll
//
#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<ll> vi;
#define FOR(i, a, b) for (ll i = (a); i<b; i++)
struct DSU {
vector<ll> e;
DSU(ll N) { e = vector<ll>(N, -1); }
// get representive component (uses path compression)
ll get(ll x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool same_set(ll a, ll b) { return get(a) == get(b); }
ll size(ll x) { return -e[get(x)]; }
bool unite(ll x, ll y) { // union by size
x = get(x), y = get(y);
if (x == y) return false;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y];
e[y] = x;
return true;
}
};
ll sz[25];
ll total = 0;
vi people(1e5 + 10);
ll dfs(ll cur, vector<vpii> &adj_ne, vector<vi> &adj_ol, ll par = -1) {
ll subt = 0;
for (auto val: adj_ne[cur]) {
if (val.f == par) continue;
ll thr = dfs(val.f, adj_ne, adj_ol, cur);
subt += thr;
total += thr * val.s;
}
for (auto val: adj_ol[cur]) {
if (val == par) continue;
subt += dfs(val, adj_ne, adj_ol, cur);
}
subt += sz[cur];
return subt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n, m, k;
cin >> n >> m >> k;
vector<pair<ll, pii> > og(m);
ll a, b, c;
FOR(i, 0, m) {
cin >> a >> b >> c;
og[i]={c, {a, b}};
}
sort(og.begin(), og.end());
vpii e;
for (auto val: og) e.pb(val.s);
DSU full(n+1);
vpii ne;
FOR(i, 0, k) {
cin >> a >> b;
ne.pb({a, b});
full.unite(a, b);
}
FOR(i, 1, n + 1) cin >> people[i];
vi merge;
FOR(i, 0, m) {
if (full.unite(e[i].f, e[i].s)) merge.pb(i);
}
// cout << merge.size() << endl;
DSU split(n + 1);
for (auto val: merge) split.unite(e[val].f, e[val].s);
// extract connected components
vi to_cc(n + 1, -1);
ll cc = 0;
FOR(i, 1, n + 1) {
if (to_cc[split.get(i)] == -1) {
to_cc[split.get(i)] = cc++;
}
// cout << i << ' '
to_cc[i] = to_cc[split.get(i)];
sz[to_cc[split.get(i)]] += people[i];
// cout << to_cc[i] << i << endl;
}
// get rep
vi rep;
set<pii> used;
vi we(k, -1);
FOR(i, 0, m) {
split.unite(e[i].f, e[i].s);
bool first=false;
FOR(j, 0, k) {
if (we[j] == -1 && split.same_set(ne[j].f, ne[j].s)) {
we[j] = og[i].f;
if (!first) rep.pb(i);
first=true;
}
}
// if (split.get(e[i].f) > split.get(e[i].s)) swap(e[i].f, e[i].s);
// if (!split.same_set(e[i].f, e[i].s) && used.find({split.get(e[i].f), split.get(e[i].s)}) == used.end()) {
// used.insert({split.get(e[i].f), split.get(e[i].s)});
// used.insert({split.get(e[i].s), split.get(e[i].f)});
// rep.pb(i);
// // cout << ' ' << i << endl;
// }
}
FOR(i, 0, k) assert(we[i] != -1);
// find weights for new edges
// FOR(i, 0, k) {
// // assert(!split.same_set(ne[i].f, ne[i].s));
// for (auto val: rep) {
// // cout << e[val].f << e[val].s << endl;
// if ((to_cc[e[val].f] == to_cc[ne[i].f] && to_cc[e[val].s] == to_cc[ne[i].s]) || (to_cc[e[val].s] == to_cc[ne[i].f] && to_cc[e[val].f] == to_cc[ne[i].s])) {
// // cout << 'd' << endl;
// // assert(we[i]==-1);
// we[i]=og[val].f;
// }
// }
// cout << i << endl;
// assert(we[i] != -1);
// }
ll ans = 0;
// cout << (1 << k) << endl;
FOR(i, 0, (1 << k)) {
DSU test(cc+1);
bool cyc=false;
vector<vpii> adj_ne(cc);
vector<vi> adj_ol(cc);
// cout << to_cc[ne[0].f] << to_cc[ne[0].s] << endl;
FOR(j, 0, k) {
if ((1 << j) & i) {
if (!test.unite(to_cc[ne[j].f], to_cc[ne[j].s])) {
cyc=true;
break;
}
adj_ne[to_cc[ne[j].f]].pb({to_cc[ne[j].s], we[j]});
adj_ne[to_cc[ne[j].s]].pb({to_cc[ne[j].f], we[j]});
}
}
if (cyc) continue;
for (auto val: rep) {
if (test.unite(to_cc[e[val].f], to_cc[e[val].s])) {
adj_ol[to_cc[e[val].f]].pb(to_cc[e[val].s]);
adj_ol[to_cc[e[val].s]].pb(to_cc[e[val].f]);
}
}
total = 0;
// cout << i << endl;
// for (auto val: adj_ne) cout << val.f << val.s << endl;
// for (auto val: adj_ol) cout << val.f << val.s << endl;
dfs(to_cc[1], adj_ne, adj_ol);
ans = max(ans, total);
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1116 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1116 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1116 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1116 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
