Submission #706496

#TimeUsernameProblemLanguageResultExecution timeMemory
706496600MihneaToll (APIO13_toll)C++17
16 / 100
4 ms324 KiB
#include <cmath> #include <functional> #include <fstream> #include <iostream> #include <vector> #include <algorithm> #include <string> #include <set> #include <map> #include <list> #include <time.h> #include <math.h> #include <random> #include <deque> #include <queue> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <cassert> #include <bitset> #include <sstream> #include <chrono> #include <cstring> #include <numeric> using namespace std; #define int long long struct Dsu { vector<int> t; int n; void init(int nn) { n = nn; t.clear(); t.resize(n); iota(t.begin(), t.end(), 0); } int root(int a) { if (t[a] == a) { return a; } else { return t[a] = root(t[a]); } } bool join(int a, int b) { a = root(a); b = root(b); if (a == b) { return 0; } t[a] = b; return 1; } }; struct Edge { int a; int b; int cost; }; bool operator < (Edge fi, Edge sc) { return fi.cost < sc.cost; } signed main() { #ifdef ONPC FILE* stream; freopen_s(&stream, "input.txt", "r", stdin); #else ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #endif int n, m, k; cin >> n >> m >> k; vector<int> people(n); vector<Edge> edges; for (int i = 1; i <= m; i++) { int a, b, cost; cin >> a >> b >> cost; a--; b--; assert(0 <= a && a < n); assert(0 <= b && b < n); edges.push_back({ a, b, cost }); } vector<pair<int, int>> spec; for (int i = 1; i <= k; i++) { int a, b; cin >> a >> b; a--; b--; assert(0 <= a && a < n); assert(0 <= b && b < n); spec.push_back({ a, b }); } for (auto& p : people) { cin >> p; } sort(edges.begin(), edges.end()); assert((int)edges.size() == m); assert((int)spec.size() == k); vector<int> ce(k, -1); set<pair<int, int>> sspec; for (int i = 0; i < k; i++) { int a = spec[i].first, b = spec[i].second; sspec.insert({a, b}); Dsu dsu; dsu.init(n); for (auto& edge : edges) { dsu.join(edge.a, edge.b); if (dsu.root(a) == dsu.root(b)) { ce[i] = edge.cost; break; } } assert(ce[i] != -1); } int sol = -1; for (int mask = 0; mask < (1 << k); mask++) { vector<int> inds; for (int bit = 0; bit < k; bit++) { if (mask & (1 << bit)) { inds.push_back(bit); } } vector<vector<pair<int, int>>> g(n); auto addedge = [&](int a, int b, int c) { assert(0 <= a && a < n); assert(0 <= b && b < n); g[a].push_back({ b, c }); g[b].push_back({ a, c }); }; bool fail = 0; Dsu dsu; dsu.init(n); for (auto& i : inds) { if (!dsu.join(spec[i].first, spec[i].second)) { fail = 1; break; } addedge(spec[i].first, spec[i].second, ce[i]); } if (fail) { continue; } for (auto& edge : edges) { if (dsu.join(edge.a, edge.b)) { addedge(edge.a, edge.b, edge.cost); } } vector<int> sub(n, 0), parof(n); int cur = 0; function<void(int, int)> build = [&](int a, int par) { parof[a] = par; sub[a] = people[a]; for (auto& it : g[a]) { int b = it.first, c = it.second; if (b == par) { continue; } build(b, a); sub[a] += sub[b]; if (sspec.count({ a, b }) || sspec.count({ b, a })) { cur += sub[b] * c; } } }; build(0, -1); for (int i = 0; i < n; i++) { for (auto& it : g[i]) { if (it.first == parof[i]) { continue; } } } //cout << " : " << cur << "\n"; sol = max(sol, cur); } cout << sol << "\n"; return 0; }
#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...