| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 438759 |
2021-06-28T14:53:34 Z |
soroush |
Toll (APIO13_toll) |
C++17 |
|
5 ms |
7628 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);
}
void merge(int x){
int v = getpar(a[x]) , u = getpar(b[x]);
if(u == v)return;
par[v] = u;
mst.pb(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];
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 ++)
merge(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]);
}
}
cout << ans;
return(0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
