Submission #1062050

#TimeUsernameProblemLanguageResultExecution timeMemory
1062050underwaterkillerwhaleToll (APIO13_toll)C++17
100 / 100
1010 ms20424 KiB
#include <bits/stdc++.h> #define ll long long #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) #define pii pair<int,int> #define pll pair<ll,ll> #define MP make_pair #define fs first #define se second #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define pb push_back #define SZ(v) (int)v.size() #define ALL(v) v.begin(),v.end() using namespace std; mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count()); ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); } const int N = 1e5 + 2; const int Mod = 1e9 + 7; const int INF = 2e9 + 7; const ll BASE = 137; const int szBL = 320; struct Disjoin_set { int lab[N], sz[N]; void init (int n) { rep (i, 1, n) lab[i] = i, sz[i] = 1; } int Find (int u) { return u == lab[u] ? u : lab[u] = Find(lab[u]); } bool Join (int u, int v) { if ((u = Find(u)) == (v = Find(v))) return 0; if (sz[u] < sz[v]) swap(u, v); sz[u] += sz[v]; lab[v] = u; return 1; } }DSU; struct Edge { int u, v, w, id; }; int n, m, K; int P[N]; pii nroad[N]; vector<int> ke[N], adj[N]; vector<Edge> delE; bool inE[(int)3e5 + 7]; ll cnt[N]; int num_cpn, cpn[N]; int mn[N], dd[N]; ll dp[N]; int high[N], par[N]; void solution () { cin >> n >> m >> K; vector<Edge> edges; rep (i, 1, m) { int u, v, w; cin >> u >> v >> w; edges.pb({u, v, w, i}); } DSU.init(n); sort (ALL(edges), [] (Edge u, Edge v) { return u.w < v.w; }); ll MST = 0; iter (&E, edges) if (DSU.Join(E.u, E.v)) inE[E.id] = 1; rep (i, 1, K) cin >> nroad[i].fs >> nroad[i].se; rep (i, 1, n) cin >> P[i]; DSU.init(n); rep (i, 1, K) { DSU.Join(nroad[i].fs, nroad[i].se); } iter (&E, edges) if (DSU.Join(E.u, E.v) == 0) { if (inE[E.id] == 1) delE.pb(E); inE[E.id] = 0; } iter (&E, edges) if (inE[E.id] == 1) { ke[E.u].pb(E.v); ke[E.v].pb(E.u); } function<void(int, int)> pdfs = [&] (int u, int p) { cnt[num_cpn] += P[u]; cpn[u] = num_cpn; iter (&v, ke[u]) { if (v == p) continue; pdfs (v, u); } }; rep (i, 1, n) { if (cpn[i]) continue; ++num_cpn; pdfs(i, 0); } rep (i, 1, K) { nroad[i].fs = cpn[nroad[i].fs]; nroad[i].se = cpn[nroad[i].se]; } iter (&E, delE) { E.u = cpn[E.u]; E.v = cpn[E.v]; } ll res = 0; function<void(int)> solve = [&] (int msk) { DSU.init(num_cpn); rep (i, 1, num_cpn) adj[i].clear(), mn[i] = 1e6 + 7, dd[i] = 0, dp[i] = 0; rep (i, 1, K) if (bit(msk, i - 1)) { if (DSU.Join(nroad[i].fs, nroad[i].se) == 0) return; adj[nroad[i].fs].pb(nroad[i].se); adj[nroad[i].se].pb(nroad[i].fs); } static vector<Edge> curE; curE.clear(); iter (&E, delE) { if (DSU.Join (E.u, E.v) == 0) curE.pb(E); else { adj[E.u].pb(E.v); adj[E.v].pb(E.u); } } function<void(int, int)> pdfs2 = [&] (int u, int p) { high[u] = high[p] + 1; par[u] = p; iter (&v, adj[u]) if (v != p) pdfs2 (v, u); }; pdfs2 (1, 0); iter (&E, curE) { int u = E.u, v = E.v, val = E.w; while (u != v) { if (high[u] > high[v]) swap(u, v); mn[v] = min(mn[v], val); v = par[v]; } } rep (i, 1, K) if (bit(msk, i - 1)) { if (high[nroad[i].fs] > high[nroad[i].se]) swap(nroad[i].fs, nroad[i].se); dd[nroad[i].se] = 1; } ll curcost = 0; function<void(int,int)> dfs2 = [&] (int u, int p) { dp[u] = cnt[u]; iter (&v, adj[u]) { if (v == p) continue; dfs2 (v, u); dp[u] += dp[v]; if (dd[v]) { curcost += dp[v] * mn[v]; } } }; dfs2(1, 0); res = max(res, curcost); }; rep (msk, 1, (1 << K) - 1) solve(msk); cout << res <<"\n"; } #define file(name) freopen(name".inp","r",stdin); \ freopen(name".out","w",stdout); int main () { // file("c"); ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int num_Test = 1; // cin >> num_Test; while (num_Test--) solution(); } /* no bug challenge +2 2 + 8 * 2 - 9 5 5 1 3 5 2 1 2 3 2 3 5 2 4 4 4 3 6 1 3 10 20 30 40 50 */

Compilation message (stderr)

toll.cpp: In lambda function:
toll.cpp:115:38: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  115 |         rep (i, 1, K) if (bit(msk, i - 1)) {
      |                                    ~~^~~
toll.cpp:10:30: note: in definition of macro 'bit'
   10 | #define bit(msk, i) ((msk >> i) & 1)
      |                              ^
toll.cpp:142:38: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  142 |         rep (i, 1, K) if (bit(msk, i - 1)) {
      |                                    ~~^~~
toll.cpp:10:30: note: in definition of macro 'bit'
   10 | #define bit(msk, i) ((msk >> i) & 1)
      |                              ^
toll.cpp: In function 'void solution()':
toll.cpp:73:8: warning: unused variable 'MST' [-Wunused-variable]
   73 |     ll MST = 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...