Submission #860701

#TimeUsernameProblemLanguageResultExecution timeMemory
860701beabossToll (APIO13_toll)C++14
16 / 100
1 ms2140 KiB
// 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); } 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; FOR(i, 0, m) { if (split.unite(e[i].f, e[i].s)) rep.pb(i); } // find weights for new edges vi we(k, -1); FOR(i, 0, k) { 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; } } 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...