| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 129132 |
2019-07-11T17:50:09 Z |
TadijaSebez |
Toll (APIO13_toll) |
C++11 |
|
6 ms |
3448 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=100050;
const int M=300050;
const int K=22;
struct DSU
{
ll sz[N];
int p[N],mark[N];
void init(){ for(int i=0;i<N;i++) p[i]=i,sz[i]=mark[i]=0;}
DSU(){ init();}
int Find(int x){ return p[x]==x?x:p[x]=Find(p[x]);}
void Union(int x, int y)
{
x=Find(x);y=Find(y);
sz[y]+=sz[x];
p[x]=y;
mark[y]|=mark[x];
}
} DS1,DS2;
struct SimpleDSU
{
int p[K*2];
void init(){ for(int i=0;i<K*2;i++) p[i]=i;}
SimpleDSU(){ init();}
int Find(int x){ return p[x]==x?x:p[x]=Find(p[x]);}
void Union(int x, int y){ p[Find(x)]=Find(y);}
} T;
int a[M],b[M],c[M],id[M],x[K],y[K];
bool was[N];
int new_name[N];
ll sz[N],sub[K*2];
vector<int> E[K*2];
int dep[K*2],par[K*2],my[K*2];
void DFS(int u, int p)
{
sub[u]=sz[u];
dep[u]=dep[p]+1;
par[u]=p;
for(int v:E[u]) if(v!=p)
{
DFS(v,u);
sub[u]+=sub[v];
}
}
void AddEdge(int u, int v){ E[u].pb(v);E[v].pb(u);}
int main()
{
int n,m,k;
scanf("%i %i %i",&n,&m,&k);
for(int i=1;i<=m;i++) scanf("%i %i %i",&a[i],&b[i],&c[i]),id[i]=i;
sort(id+1,id+1+m,[&](int i, int j){ return c[i]<c[j];});
for(int i=1;i<=k;i++) scanf("%i %i",&x[i],&y[i]),DS1.mark[x[i]]=DS1.mark[y[i]]=1;
for(int i=1;i<=n;i++) scanf("%lld",&DS1.sz[i]);
vector<int> es;
for(int j=1;j<=m;j++)
{
int i=id[j];
if(DS2.Find(a[i])!=DS2.Find(b[i]))
{
if(DS1.mark[DS1.Find(a[i])]+DS1.mark[DS1.Find(b[i])]<2) DS1.Union(a[i],b[i]);
else es.pb(i);
DS2.Union(a[i],b[i]);
}
}
int nsz=0;
for(int i=1;i<=n;i++)
{
if(!was[DS1.Find(i)])
{
was[DS1.Find(i)]=1;
new_name[DS1.Find(i)]=++nsz;
sz[nsz]=DS1.sz[DS1.Find(i)];
}
}
for(int i=1;i<=m;i++)
{
a[i]=new_name[DS1.Find(a[i])];
b[i]=new_name[DS1.Find(b[i])];
}
for(int i=1;i<=k;i++)
{
x[i]=new_name[DS1.Find(x[i])];
y[i]=new_name[DS1.Find(y[i])];
}
ll ans=0;
for(int mask=1;mask<(1<<k);mask++)
{
for(int i=1;i<=nsz;i++) T.p[i]=i,my[i]=0,E[i].clear();
bool ok=1;
for(int i=1;i<=k;i++) if(mask>>(i-1)&1)
{
if(T.Find(x[i])!=T.Find(y[i]))
{
T.Union(x[i],y[i]);
AddEdge(x[i],y[i]);
}
else{ ok=0;break;}
}
if(!ok) continue;
vector<int> up;
for(int i:es)
{
if(T.Find(a[i])!=T.Find(b[i]))
{
T.Union(a[i],b[i]);
AddEdge(a[i],b[i]);
}
else up.pb(i);
}
DFS(1,0);
for(int x:up)
{
int u=a[x],v=b[x];
if(dep[u]<dep[v]) swap(u,v);
for(;dep[u]>dep[v];u=par[u]) if(!my[u]) my[u]=x;
for(;u!=v;u=par[u],v=par[v])
{
if(!my[u]) my[u]=x;
if(!my[v]) my[v]=x;
}
}
ll sum=0;
for(int i=1;i<=k;i++)
{
int u=x[i];
if(dep[u]<dep[y[i]]) u=y[i];
sum+=(ll)c[my[u]]*sub[u];
}
ans=max(ans,sum);
}
printf("%lld\n",ans);
return 0;
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i %i",&n,&m,&k);
~~~~~^~~~~~~~~~~~~~~~~~~~~
toll.cpp:53:59: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=m;i++) scanf("%i %i %i",&a[i],&b[i],&c[i]),id[i]=i;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
toll.cpp:55:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=k;i++) scanf("%i %i",&x[i],&y[i]),DS1.mark[x[i]]=DS1.mark[y[i]]=1;
~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:56:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++) scanf("%lld",&DS1.sz[i]);
~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
3448 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
3448 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
3448 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
3448 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
