# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
726327 |
2023-04-18T18:01:40 Z |
vjudge1 |
Toll (APIO13_toll) |
C++17 |
|
1679 ms |
13824 KB |
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define lastbit(i) __builtin_ctz(i)
const int maxn=1e5+9;
const int maxm=3e5+9;
long long val[maxn];
struct edg{
int u,v;
long long w;
bool operator < (const edg &p){
return w<p.w;
}
};
vector<edg>realneed;
edg b[maxm],c[20];
int num[maxn];
struct DSU{
vector<int>a;
int n;
void resz(int _n){
n=_n;
a.resize(n+1);
for1(i,1,n)a[i]=-1;
}
int findset(int u){
if (a[u]<0)return u;
return a[u]=findset(a[u]);
}
bool unite(int u,int v){
u=findset(u),v=findset(v);
if (u==v)return 0;
if (a[u]<a[v])swap(u,v);
a[u]+=a[v];
//val[u]+=val[v];
a[v]=u;
return 1;
}
};
long long sub[109];
int cc=0;
int n,m,k;
vector<pii>a[109];
long long newsub[109];
long long mmb[109];
int par[109];
int dis[109];
void dfs(int u,int p){
for (auto v:a[u]){
if (v.fi==p)continue;
par[v.fi]=u;
if (!v.se)mmb[v.fi]=1e6;
dis[v.fi]=dis[u]+1;
dfs(v.fi,u);
newsub[u]+=newsub[v.fi];
}
}
void minimize(edg temp){
int u=temp.u,v=temp.v;
while (dis[v]>dis[u]){
mmb[v]=min(mmb[v],temp.w);
v=par[v];
}
while (dis[u]>dis[v]){
mmb[u]=min(mmb[u],temp.w);
u=par[u];
}
while (u!=v){
mmb[u]=min(mmb[u],temp.w);
mmb[v]=min(mmb[v],temp.w);
u=par[u];
v=par[v];
}
}
long long cal(int mask){
DSU temp;
temp.resz(cc);
for1(i,1,cc)a[i].clear();
for1(i,1,cc){
newsub[i]=sub[i];
par[i]=0;
mmb[i]=0;
dis[i]=0;
}
for1(i,0,k-1){
if (mask>>i&1){
if (temp.unite(c[i].u,c[i].v)){
a[c[i].u].pb({c[i].v,0});
a[c[i].v].pb({c[i].u,0});
}
else return 0;
}
}
vector<edg>notuse;
for (auto v:realneed){
if (temp.unite(v.u,v.v)){
a[v.u].pb({v.v,1});
a[v.v].pb({v.u,1});
}
else notuse.pb(v);
}
dfs(num[1],0);
for (auto v:notuse){
minimize(v);
//cout<<v.u<<" "<<v.v<<" "<<v.w<<'\n';
}
long long ans=0;
for1(i,1,cc){
ans+=1ll*mmb[i]*newsub[i];
}
//cout<<mmb[1]<<" "<<newsub[1]<<'\n';
return ans;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen(".INP","r",stdin);
//freopen(".OUT","w",stdout);
cin>>n>>m>>k;
DSU m1,m2,real;
m1.resz(n);
m2.resz(n);
real.resz(n);
for1(i,1,m){
cin>>b[i].u>>b[i].v>>b[i].w;
}
sort(b+1,b+1+m);
for1(i,0,k-1){
cin>>c[i].u>>c[i].v;
}
for1(i,1,n)cin>>val[i];
for1(i,0,k-1){
m1.unite(c[i].u,c[i].v);
}
for1(i,1,m){
bool fl=false;
if (real.unite(b[i].u,b[i].v)){
fl=true;
}
if (m1.unite(b[i].u,b[i].v)){
m2.unite(b[i].u,b[i].v);
//cout<<b[i].u<<" "<<b[i].v<<'\n';
}
else {
if (fl){
realneed.pb(b[i]);
}
}
}
for1(i,1,n){
if (m2.a[i]<0){
num[i]=++cc;
}
}
for1(i,1,n){
num[i]=num[m2.findset(i)];
sub[num[i]]+=val[i];
}
for1(i,0,k-1){
c[i].u=num[c[i].u];
c[i].v=num[c[i].v];
}
for (auto &v:realneed){
v.u=num[v.u];
v.v=num[v.v];
//cout<<v.u<<" "<<v.v<<'\n';
}
long long ans=0;
for1(i,0,(1<<k)-1){
ans=max(ans,cal(i));
}
cout<<ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
3 ms |
440 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
3 ms |
440 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
183 ms |
7480 KB |
Output is correct |
8 |
Correct |
181 ms |
7368 KB |
Output is correct |
9 |
Correct |
189 ms |
7356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
3 ms |
440 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
183 ms |
7480 KB |
Output is correct |
8 |
Correct |
181 ms |
7368 KB |
Output is correct |
9 |
Correct |
189 ms |
7356 KB |
Output is correct |
10 |
Correct |
1369 ms |
7372 KB |
Output is correct |
11 |
Correct |
1677 ms |
13760 KB |
Output is correct |
12 |
Correct |
1679 ms |
13824 KB |
Output is correct |