Submission #1165276

#TimeUsernameProblemLanguageResultExecution timeMemory
1165276KerimToll (APIO13_toll)C++20
56 / 100
20 ms3908 KiB
#include "bits/stdc++.h" #define ll long long #define ff first #define ss second #define edgew pair<int, pair<int,int> > #define edge pair<int,int> using namespace std; struct connectivity{ vector<int> ata; vector<int> sz; int n; connectivity(int _n){ n = _n; ata.resize(n+1); sz.resize(n+1); } void init(){ for (int i = 1; i <= n; i++) ata[i] = i, sz[i] = 1; } int tap(int x){ if (ata[x] == x) return x; return ata[x] = tap(ata[x]); } bool merge(int x, int y){ if ((x=tap(x)) == (y=tap(y))) return 0; if (sz[x] < sz[y]) swap(x, y); ata[y] = x; sz[x] += sz[y]; return 1; } bool is_connected(int x, int y){ return tap(x) == tap(y); } vector<int> get_components(){ vector<int> components; for (int i = 1; i <= n; i++) if (ata[i] == i) components.push_back(i); return components; } }; const int N = 1e5+5; const int K = 20; const int INF = 1e9; edgew black_edges[N]; edge blue_edges[K]; int a[N]; vector<int> adj[N]; void add_edge(int u, int v){ adj[u].push_back(v); adj[v].push_back(u); } ll sub[N]; int par[N], lvl[N], l[N]; void dfs(int nd, int pr){ par[nd] = pr; sub[nd] = a[nd]; for (auto to: adj[nd]) if (to != pr){ lvl[to] = lvl[nd]+1; dfs(to, nd); sub[nd] += sub[to]; } } void upd(int u, int v, int w){ while (u != v){ if (lvl[u] > lvl[v]) swap(u, v); l[v] = min(l[v], w); v = par[v]; } } int main(){ // freopen("file.in", "r", stdin); int n, m, k; scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= m; i++){ int u, v, w; scanf("%d%d%d", &u, &v, &w); black_edges[i] = {w, {u, v}}; } sort(black_edges+1, black_edges+m+1); connectivity dsu(n); dsu.init(); // black edges vector<edgew> selected; for (int i = 1; i <= m; i++){ int w = black_edges[i].ff; int u = black_edges[i].ss.ff; int v = black_edges[i].ss.ss; if (dsu.merge(u, v)) selected.push_back(black_edges[i]); } for (int i = 0; i < k; i++){ int u, v; scanf("%d%d", &u, &v); blue_edges[i] = {u, v}; } for (int i = 1; i <= n; i++) scanf("%d", a+i); ll ans = 0; //O(2^k*nlogn) for (int mask = 0; mask < (1<<k); mask++){ dsu.init(); for (int i = 1; i <= n; i++) adj[i].clear(), l[i] = INF; bool valid = true; for (int i = 0; i < k; i++) if (mask>>i&1){ auto [u, v] = blue_edges[i]; add_edge(u, v); if (!dsu.merge(u, v)) valid = false; } if (!valid) continue; vector<bool> state(selected.size(), 0); for (int i = 0; i < selected.size(); i++){ int u = selected[i].ss.ff; int v = selected[i].ss.ss; state[i] = dsu.merge(u, v); if (state[i]) add_edge(u, v); } dfs(1, -1); for (int i = 0; i < selected.size(); i++){ int w = selected[i].ff; int u = selected[i].ss.ff; int v = selected[i].ss.ss; if (!state[i]) upd(u, v, w); } ll value = 0; for (int i = 0; i < k; i++) if (mask>>i&1){ auto [u, v] = blue_edges[i]; add_edge(u, v); if (lvl[u] > lvl[v]) swap(u, v); value += l[v] * sub[v]; } ans = max(ans, value); } printf("%lld\n", ans); }

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf("%d%d%d", &n, &m, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:85:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |                 scanf("%d%d%d", &u, &v, &w);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:102:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |                 scanf("%d%d", &u, &v);
      |                 ~~~~~^~~~~~~~~~~~~~~~
toll.cpp:106:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |                 scanf("%d", a+i);
      |                 ~~~~~^~~~~~~~~~~
#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...