| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 438800 |
2021-06-28T15:53:24 Z |
soroush |
Toll (APIO13_toll) |
C++17 |
|
5 ms |
7372 KB |
#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
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 time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
