Submission #1061523

#TimeUsernameProblemLanguageResultExecution timeMemory
1061523underwaterkillerwhaleToll (APIO13_toll)C++17
0 / 100
1 ms6488 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 ll INF = 2e9 + 7; const ll BASE = 137; const int szBL = 320; const int N2 = 1e5 + 7; struct Disjoint_set_U { 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) { u = Find(u); v = Find(v); if (u == v) return 0; if (sz[u] < sz[v]) swap (u, v); sz[u] += sz[v]; lab[v] = u; return 1; } }DSU, DSU2; struct Edge { int u, v, w; }; int n, m, K; ll P[N]; pii road[N]; vector<int> ke[N]; int high[N]; ll dp[N]; ll res = 0; void dfs (int u, int p, ll delta) { dp[u] = P[u]; iter (&v, ke[u]) { if (v == p) continue; dfs (v, u, delta); dp[u] += dp[v]; pii cur = {u, v}; if (u > v) swap (u, v); // cout << u << " "<<v<<"\n"; if (MP(u, v) == road[1]) res = dp[v] * delta; } } 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}); } DSU.init(n); sort (ALL(edges), [] (Edge a, Edge b){ return a.w < b.w; }); ll MST = 0; iter (&E, edges) { if (DSU.Join(E.u, E.v)) { MST += E.w; } } cin >> road[1].fs >> road[1].se; rep (i, 1, n) cin >> P[i]; if (road[1].fs > road[1].se) swap(road[1].fs, road[1].se); DSU.init(n); DSU.Join(road[1].fs, road[1].se); ke[road[1].fs].pb(road[1].se); ke[road[1].se].pb(road[1].fs); ll MST2 = 0; iter (&E, edges) { if (DSU.Join(E.u, E.v)) { MST2 += E.w; ke[E.u].pb(E.v); ke[E.v].pb(E.u); } } ll delta = MST - MST2; cout << delta <<"\n"; dfs(1, 0, delta); 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 function 'void dfs(int, int, long long int)':
toll.cpp:65:13: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
   65 |         pii cur = {u, v};
      |             ^~~
#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...