제출 #366201

#제출 시각아이디문제언어결과실행 시간메모리
366201zaneyu통행료 (APIO13_toll)C++14
16 / 100
122 ms163844 KiB
/*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 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...