| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 385522 |
2021-04-04T14:23:42 Z |
ogibogi2004 |
Toll (APIO13_toll) |
C++14 |
|
1 ms |
620 KB |
#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
int n,m,k;
struct edge
{
int u,v,w;
bool operator<(edge const& other)const
{
return w<other.w;
}
};
int ans,sum;
vector<edge>e;
vector<edge>nmst;
vector<edge>mst;
int st[20],en[20];
vector<pair<int,int> >g[1024];
int par[1024],sz[1024];
int dp1[1024][12];
int depth[1024];
int h[1024];
vector<int>spec[1024][12];
int getRoot(int u)
{
if(u==par[u])return u;
return par[u]=getRoot(par[u]);
}
void join(int p,int q)
{
if(sz[p]>sz[q])
{
par[q]=p;
sz[p]+=sz[q];
}
else
{
par[p]=q;
sz[q]+=sz[p];
}
}
void dfs(int u,int p,int 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(int step=0;step<10;step++)
{
for(int 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<int> on_path(int x,int y)
{
if(depth[x]<depth[y])swap(x,y);
int diff=depth[x]-depth[y];
vector<int>ret;
for(int 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(int 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;
}
int res[22];
int sbt[1024];
void dfs1(int u,int 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(int mask)
{
for(int i=1;i<=n;i++)
{
g[i].clear();
par[i]=i;sz[i]=1;
for(int j=0;j<12;j++)spec[i][j].clear();
}
mst.clear();
nmst.clear();
for(int i=0;i<k;i++)
{
if(mask&(1<<i))
{
int p=getRoot(st[i]);
int q=getRoot(en[i]);
if(p==q)return;
join(p,q);
mst.push_back({st[i],en[i],-i});
}
}
for(auto ed:e)
{
int p=getRoot(ed.u);
int q=getRoot(ed.v);
if(p==q)
{
nmst.push_back(ed);
continue;
}
join(p,q);
mst.push_back(ed);
}
for(int 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(int i=0;i<=k;i++)res[i]=INF;
for(auto xd:nmst)
{
vector<int>v=on_path(xd.u,xd.v);
for(auto dx:v)
{
res[dx]=min(res[dx],xd.w);
}
}
for(int i=0;i<1024;i++)sbt[i]=0;
sum=0;
dfs1(1,0);
ans=max(ans,sum);
}
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
e.push_back({x,y,z});
}
sort(e.begin(),e.end());
for(int i=0;i<k;i++)
{
cin>>st[i]>>en[i];
}
for(int i=1;i<=n;i++)cin>>h[i];
for(int 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(int)':
toll.cpp:155:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | for(int 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 |
- |
