| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 366201 |
2021-02-13T13:38:28 Z |
zaneyu |
Toll (APIO13_toll) |
C++14 |
|
122 ms |
163844 KB |
/*input
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
*/
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("unroll-loo8ps,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
#define ll long long
#define ld long double
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FIlim(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll INF64=4e18;
const ll INF=0x3f3f3f3f;
const ll MOD=1e9+7;
//const ld PI=acos(-1);
const ld eps=1e-9;
const int maxn=1e5+5;
const int maxlg=__lg(maxn)+2;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define FILL(x,y) memset(x,y,sizeof(x))
inline ll mult(ll a,ll b){
a%=MOD,b%=MOD;
return (a*b)%MOD;
}
inline ll mypow(ll a,ll b){
if(b<=0) return 1;
a%=MOD;
ll res=1;
while(b){
if(b&1) res=mult(res,a);
a=mult(a,a);
b>>=1;
}
return res;
}
ll st[maxn];
ll csz[maxn];
ll tmp[maxn];
struct UFDS{
int par1[maxn];
void init(int n){
REP(i,n) par1[i]=i;
}
int find(int u){
if(par1[u]==u) return par1[u];
return par1[u]=find(par1[u]);
}
void merge(int a,int b){
a=find(a),b=find(b);
par1[a]=b;
}
}uf;
vector<pii> v[maxn];
vector<pii> g[maxn];
int comp[maxn];
int par[maxn],pae[maxn],dep[maxn],arr[maxn];
void dfs(int u,int c){
csz[c]+=arr[u];
for(auto x:v[u]){
if(!comp[x.f]){
comp[x.f]=c;
dfs(x.f,c);
}
}
}
void dfs2(int u,int p){
for(auto x:v[u]){
if(x.f!=p){
dep[x.f]=dep[u]+1;
par[x.f]=u;
pae[x.f]=INF;
dfs2(x.f,u);
tmp[u]+=tmp[x.f];
}
}
}
int32_t main(){
ios::sync_with_stdio(false),cin.tie(0);
int n,m,k;
cin>>n>>m>>k;
vector<pair<int,pii>> edge;
REP(i,m){
int a,b,c;
cin>>a>>b>>c;
--a;
--b;
edge.pb({c,{a,b}});
}
uf.init(n);
ll ans=0;
vector<pii> nw;
REP(i,k){
int a,b;
cin>>a>>b;
--a;
--b;
nw.pb({a,b});
edge.pb({-INF,{a,b}});
}
sort(ALL(edge));
REP(i,n) cin>>arr[i];
for(auto x:edge){
int a=x.s.f,b=x.s.s;
if(uf.find(a)!=uf.find(b)){
uf.merge(a,b);
if(x.f!=-INF){
v[a].pb({b,x.f});
v[b].pb({a,x.f});
}
}
}
int cnt=0;
REP(i,n){
if(!comp[i]){
comp[i]=++cnt;
dfs(i,cnt);
}
}
uf.init(cnt+1);
vector<pair<int,pii>> left;
for(auto x:edge){
int a=x.s.f,b=x.s.s;
if(comp[a]==comp[b] or x.f==-INF) continue;
if(uf.find(comp[a])!=uf.find(comp[b])){
uf.merge(comp[a],comp[b]);
if(x.f!=-INF){
left.pb({x.f,{comp[a],comp[b]}});
}
}
}
for(auto &x:nw) x.f=comp[x.f],x.s=comp[x.s];
REP(i,n) v[i].clear(),v[i].shrink_to_fit();
REP1(msk,(1<<k)-1){
REP(j,cnt+1) v[j].clear(),tmp[j]=csz[j];
uf.init(cnt+1);
REP(i,k){
if(msk&(1<<i)){
uf.merge(nw[i].f,nw[i].s);
v[nw[i].f].pb({nw[i].s,edge[i].f});
v[nw[i].s].pb({nw[i].f,edge[i].f});
}
}
vector<pair<int,pii>> l2;
for(auto x:left){
if(uf.find(x.s.f)!=uf.find(x.s.s)){
v[x.s.f].pb({x.s.s,x.f});
v[x.s.s].pb({x.s.f,x.f});
}
else{
l2.pb(x);
}
}
dfs2(1,-1);
for(auto x:l2){
int a=x.s.f,b=x.s.s;
if(dep[a]<dep[b]) swap(a,b);
while(dep[a]<dep[b]){
MNTO(pae[a],x.f);
a=par[a];
}
while(a!=b){
MNTO(pae[a],x.f);
MNTO(pae[b],x.f);
a=par[a];
b=par[b];
}
}
ll cur=0;
REP(i,k){
if(msk&(1<<i)){
if(tmp[nw[i].f]>tmp[nw[i].s]) swap(nw[i].f,nw[i].s);
cur+=tmp[nw[i].f]*pae[nw[i].f];
}
}
MXTO(ans,cur);
}
cout<<ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 3 |
Runtime error |
122 ms |
163844 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 3 |
Runtime error |
122 ms |
163844 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 3 |
Runtime error |
122 ms |
163844 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 3 |
Runtime error |
122 ms |
163844 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
