| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 385523 |
2021-04-04T14:24:47 Z |
ogibogi2004 |
Toll (APIO13_toll) |
C++14 |
|
1 ms |
620 KB |
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=1e16;
ll n,m,k;
struct edge
{
ll u,v,w;
bool operator<(edge const& other)const
{
return w<other.w;
}
};
ll ans,sum;
vector<edge>e;
vector<edge>nmst;
vector<edge>mst;
ll st[20],en[20];
vector<pair<ll,ll> >g[1024];
ll par[1024],sz[1024];
ll dp1[1024][12];
ll depth[1024];
ll h[1024];
vector<ll>spec[1024][12];
ll getRoot(ll u)
{
if(u==par[u])return u;
return par[u]=getRoot(par[u]);
}
void join(ll p,ll q)
{
if(sz[p]>sz[q])
{
par[q]=p;
sz[p]+=sz[q];
}
else
{
par[p]=q;
sz[q]+=sz[p];
}
}
void dfs(ll u,ll p,ll s)
{
dp1[u][0]=p;
depth[u]=depth[p]+1;
if(s>=0)spec[u][0].push_back(s);
for(auto xd:g[u])
{
if(xd.first==p)continue;
if(xd.second>0)dfs(xd.first,u,-1);
else dfs(xd.first,u,-xd.second);
}
}
void precompute()
{
for(ll step=0;step<10;step++)
{
for(ll i=1;i<=n;i++)
{
spec[i][step+1]=spec[i][step];
for(auto xd:spec[dp1[i][step]][step])
{
spec[i][step+1].push_back(xd);
}
dp1[i][step]=dp1[dp1[i][step]][step];
}
}
}
vector<ll> on_path(ll x,ll y)
{
if(depth[x]<depth[y])swap(x,y);
ll diff=depth[x]-depth[y];
vector<ll>ret;
for(ll i=0;i<12;i++)
{
if(diff&(1<<i))
{
for(auto xd:spec[x][i])
{
ret.push_back(xd);
}
x=dp1[x][i];
}
}
if(x==y)return ret;
for(ll i=11;i>=0;i--)
{
if(dp1[x][i]!=dp1[y][i])
{
for(auto xd:spec[x][i])
{
ret.push_back(xd);
}
for(auto xd:spec[y][i])
{
ret.push_back(xd);
}
x=dp1[x][i];
y=dp1[y][i];
}
}
for(auto xd:spec[x][0])ret.push_back(xd);
for(auto xd:spec[y][0])ret.push_back(xd);
return ret;
}
ll res[22];
ll sbt[1024];
void dfs1(ll u,ll p)
{
sbt[u]=h[u];
for(auto xd:g[u])
{
if(xd.first==p)continue;
dfs1(xd.first,u);
if(xd.second<=0)
{
sum+=sbt[xd.first]*res[-xd.second];
}
sbt[u]+=sbt[xd.first];
}
}
void check(ll mask)
{
for(ll i=1;i<=n;i++)
{
g[i].clear();
par[i]=i;sz[i]=1;
for(ll j=0;j<12;j++)spec[i][j].clear();
}
mst.clear();
nmst.clear();
for(ll i=0;i<k;i++)
{
if(mask&(1<<i))
{
ll p=getRoot(st[i]);
ll q=getRoot(en[i]);
if(p==q)return;
join(p,q);
mst.push_back({st[i],en[i],-i});
}
}
for(auto ed:e)
{
ll p=getRoot(ed.u);
ll q=getRoot(ed.v);
if(p==q)
{
nmst.push_back(ed);
continue;
}
join(p,q);
mst.push_back(ed);
}
for(ll i=0;i<mst.size();i++)
{
g[mst[i].u].push_back({mst[i].v,mst[i].w});
g[mst[i].v].push_back({mst[i].u,mst[i].w});
}
dfs(1,0,0);
precompute();
for(ll i=0;i<=k;i++)res[i]=INF;
for(auto xd:nmst)
{
vector<ll>v=on_path(xd.u,xd.v);
for(auto dx:v)
{
res[dx]=min(res[dx],xd.w);
}
}
for(ll i=0;i<1024;i++)sbt[i]=0;
sum=0;
dfs1(1,0);
ans=max(ans,sum);
}
int main()
{
cin>>n>>m>>k;
for(ll i=1;i<=m;i++)
{
ll x,y,z;
cin>>x>>y>>z;
e.push_back({x,y,z});
}
sort(e.begin(),e.end());
for(ll i=0;i<k;i++)
{
cin>>st[i]>>en[i];
}
for(ll i=1;i<=n;i++)cin>>h[i];
for(ll mask=0;mask<(1<<k);mask++)
{
check(mask);
}
cout<<ans<<endl;
return 0;
}
/*
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
*/
Compilation message
toll.cpp: In function 'void check(long long int)':
toll.cpp:156:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | for(ll i=0;i<mst.size();i++)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
