Submission #438800

#TimeUsernameProblemLanguageResultExecution timeMemory
438800soroushToll (APIO13_toll)C++17
0 / 100
5 ms7372 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int , int> pii; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxn = 1e5 + 10; const ll mod = 1e9+7; #define pb push_back #define endl '\n' #define dokme(x) cout << x , exit(0) #define ms(x , y) memset(x , y , sizeof x) ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);} int n, m, k; vector < int > adj[maxn] , mst; vector < pii > e; int a[maxn] , b[maxn] , c[maxn] , p[maxn] , srt[maxn] , par[maxn]; int getpar(int v){ return ((par[v]) ? par[v] = getpar(par[v]) : v); } ll marg(int x){ int v = getpar(a[x]) , u = getpar(b[x]); if(u == v)return 0; par[v] = u; return c[x]; } ll fish[maxn] , dish; ll merge(int x){ int v = getpar(a[x]) , u = getpar(b[x]); if(u == v)return 0; fish[u] += fish[v]; par[v] = u; return c[x]; } const int lg = 20; struct LCA{ int n; int par[lg+3][maxn] , h[maxn]; vector < pii > adj[maxn]; ll H[maxn] , sum[maxn]; void dfs(int v , int pr){ sum[v] += p[v]; for(auto [u, w] : adj[v]) if(u ^ pr) H[u] = H[v] + w , h[u] = h[v] + 1 , par[0][u] = v , dfs(u , v) , sum[v] += sum[u]; } void init(int N , int root = 1){ n = N; dfs(root , 0); h[0] = -1; for(int j = 1 ; j <= lg ; j ++) for(int i = 1 ; i <= n ; i ++) par[j][i] = par[j - 1][par[j - 1][i]]; } int lca(int u , int v){ if(h[u] < h[v]) swap(u , v); for(int i = lg ; i >= 0 ; i --) if(h[par[i][u]] >= h[v]) u = par[i][u]; if(u == v) return(u); for(int i = lg ; i >= 0 ; i --) if(par[i][u] ^ par[i][v]) u = par[i][u] , v = par[i][v]; return(par[0][v]); } int uwdist(int u , int v){ return h[u] + h[v] - 2 * h[lca(u , v)]; } int dist(int u , int v){ return(H[u] + H[v] - 2*H[lca(u , v)]); } }lc, cur; int32_t main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin >> n >> m >> k; for(int i = 0 ; i < m ; i ++){ cin >> a[i] >> b[i] >> c[i]; adj[a[i]].pb(i), adj[b[i]].pb(i); srt[i] = i; } for(int i = 0 , u , v ; i < k ; i ++) cin >> u >> v, e.pb({u , v}); for(int i = 1 ; i <= n ; i ++) cin >> p[i] , dish += p[i]; /* sort(srt , srt + n , [](int i , int j){return c[i] < c[j];}); for(int i = 1 ; i <= n ; i ++) sort(adj[i].begin(), adj[i].end() , [](int i, int j){return c[i] < c[j];}); for(int i = 0 ; i < m ; i ++) marg(srt[i]); ll sum = 0; for(int x : mst){ //lc.adj[a[x]].pb({b[x] , c[x]}); //lc.adj[b[x]].pb({a[x] , c[x]}); sum += c[x]; } */ //lc.init(n); ll ans = 0; /* for(int i = 0 ; i < (1 << k) ; i ++){ bool ok = 1; for(int j = 0 ; j < k ; j ++)if(i & (1 << j)){ int u = e[j].first, v = e[j].second; if(getpar(u) == getpar(v)){ ok = 0; for(auto [a, b] : e)par[a] = par[b] = 0; break; } par[getpar(v)] = getpar(u); } if(!ok)continue; for(int j = 0 ; j < k ; j ++)if(i & (1 << j)){ int u = e[j].first, v = e[j].second; cur.adj[u].pb({v, 0}) , cur.adj[v].pb({u , 0}); } mst.clear(); for(int i = 0 ; i < m ; i ++) merge(srt[i]); for(int x : mst){ cur.adj[a[x]].pb({b[x] , c[x]}); cur.adj[b[x]].pb({a[x] , c[x]}); sum -= c[x]; } cur.init(n); for(int i = 1 ; i <= n ; i ++)par[i] = 0; for(int j = 0 ; j < k ; j ++)if(i & (1 << j)){ int u = e[j].first, v = e[j].second; int lca = cur.lca(u, v); ans += sum * (cur.sum[u ^ v ^ lca]); } } */ assert(k == 1); auto [u, v] = e[0]; /* for(int i = 0 ; i < (1 << m) ; i ++)if(__builtin_popcount(i) == n - 2){ for(int j = 1 ; j <= n ; j ++)par[j] = 0 , fish[j] = p[j]; ll cur = 0; for(int j = 0 ; j < m ; j ++)if((1 << j) & i){ cur += c[j]; if(getpar(a[j]) == getpar(b[j])){ cur += 1e14; break; } fish[getpar(b[j])] += fish[getpar(a[j])]; par[getpar(a[j])] = getpar(b[j]); } if(getpar(u) == getpar(v))continue; bitset < 10 > bs = i; if((sum - cur) * (dish - fish[getpar(1)]) == 420)dokme(sum); ans = max(ans , (sum - cur) * (dish - fish[getpar(1)])); } */ /* for(int i = 0 ; i < (1 << n) ; i ++){ int x = i << 1; for(int j = 1 ; j <= n ; j ++)par[j] = 0 , fish[j] = p[j]; ll cur = 0 , mn = 1e9; int cnt = 0; for(int j = 0 ; j < m ; j ++){ if(x & (1 << a[j]) and x & (1 << b[j])){ if(getpar(a[j])^getpar(b[j]))cur += c[j], cnt++; mn = min(mn , merge(j)); //cnt ++; //if(i == 7)dokme(j); } else if((x & (1 << a[j])) == 0 and (x & (1 << b[j])) == 0){ if(getpar(a[j])^getpar(b[j]))cur += c[j] , cnt++; mn = min(mn , merge(j)); //cnt ++; //if(i == 7)dokme(j); } else{ //if(i == 11)dokme((x & (1 << a[j]))); mn = min(mn , 1ll * c[j]); } }//if(i == 11)dokme((getpar(u) == getpar(v))); if(cnt != n - 2)continue; if(getpar(u) == getpar(v))continue; //if( i == 11)dokme("wtF"); //if(i == 11)dokme(sum); if(cur + mn <= sum){ //if(i == 1)dokme('d'); ans = max(ans , mn * (dish - fish[getpar(1)])); if(ans == 420)dokme(x); } } */ int l = 0 , r = 1e9; a[m] = u , b[m] = v; srt[m] = m; for(int i = 0 ; i < m ; i ++){ c[m] = c[i]; sort(srt , srt + m , [](int i , int j){return c[i] < c[j];}); ll sum = 0; for(int i = 1 ; i <= n ; i ++)par[i] = 0 , fish[i] = p[i]; for(int i = 0 ; i <= m ; i ++)sum += merge(i); for(int i = 1 ; i <= n ; i ++)par[i] = 0 , fish[i] = p[i]; sum -= merge(m); int x = 0; for(int i = 0 ; i < m ; i ++){ ll pq = sum; sum -= merge(i); if(pq ^ sum)x|= (1 << i); } if(sum == 0){ //dokme(2); for(int i = 1 ; i <= n ; i ++)par[i] = 0 , fish[i] = p[i]; for(int i = 0 ; i < m ; i ++)if((1 << i) & x)merge(i); ans = max(ans , c[i] * 1ll * (dish - fish[getpar(1)])); } } cout << ans; return(0); }

Compilation message (stderr)

toll.cpp: In function 'int32_t main()':
toll.cpp:208:6: warning: unused variable 'l' [-Wunused-variable]
  208 |  int l = 0 , r = 1e9;
      |      ^
toll.cpp:208:14: warning: unused variable 'r' [-Wunused-variable]
  208 |  int l = 0 , r = 1e9;
      |              ^
#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...