| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1106219 |
2024-10-29T14:36:02 Z |
vivkostov |
Toll (APIO13_toll) |
C++14 |
|
1 ms |
4432 KB |
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
void speed()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
struct cell
{
int a,b,c,in;
};
bool cmp(cell a1,cell a2)
{
return a1.c<a2.c;
}
int n,m,k,br[100005],sz[100005],lead[100005],used[30],val[100005],has1[100005],otg,mult[100005];
vector<int>nhas1;
cell edge[300005],edge1[300005];
stack<cell>s;
void prec()
{
has1[1]=1;
for(int i=1;i<=n;i++)
{
lead[i]=i;
sz[i]=1;
val[i]=br[i];
}
}
int get_lead(int beg)
{
if(lead[beg]==beg)return beg;
return get_lead(lead[beg]);
}
void add(cell ed)
{
int a=ed.a,b=ed.b;
int la=get_lead(a),lb=get_lead(b);
if(la==lb)return;
for(int i=1;i<=k;i++)
{
int l1=get_lead(edge1[i].a),l2=get_lead(edge1[i].b);
if(max(la,lb)==max(l1,l2)&&min(la,lb)==min(l1,l2))
{
edge1[i].c=ed.c;
}
}
if(sz[la]<sz[lb])swap(la,lb);
ed.a=la;
ed.b=lb;
s.push(ed);
sz[la]+=sz[lb];
lead[lb]=la;
}
void add2(cell ed,int in)
{
int a=ed.a,b=ed.b;
int la=get_lead(a),lb=get_lead(b);
if(la==lb)return;
for(int i=1;i<=k;i++)
{
int l1=get_lead(edge1[i].a),l2=get_lead(edge1[i].b);
if(max(la,lb)==max(l1,l2)&&min(la,lb)==min(l1,l2))
{
if(!edge1[i].in)edge1[i].in=in;
return;
}
}
if(sz[la]<sz[lb])swap(la,lb);
ed.a=la;
ed.b=lb;
s.push(ed);
sz[la]+=sz[lb];
val[la]+=val[lb];
has1[la]=max(has1[la],has1[lb]);
lead[lb]=la;
}
void add3(cell ed)
{
int a=ed.a,b=ed.b;
int la=get_lead(a),lb=get_lead(b);
if(la==lb)return;
if(sz[la]<sz[lb])swap(la,lb);
ed.a=la;
ed.b=lb;
s.push(ed);
sz[la]+=sz[lb];
val[la]+=val[lb];
has1[la]=max(has1[la],has1[lb]);
lead[lb]=la;
}
void rem()
{
int a=s.top().a,b=s.top().b;
lead[b]=b;
sz[a]-=sz[b];
val[a]-=val[b];
if(has1[b]==1)has1[a]=0;
s.pop();
}
void find_c()
{
prec();
for(int i=1;i<=m;i++)
{
add(edge[i]);
}
prec();
}
void check()
{
for(int i=1;i<=n;i++)
{
cout<<i<<" "<<lead[i]<<" "<<sz[i]<<" "<<has1[i]<<endl;
}
cout<<endl;
}
void addperm()
{
for(int i=1;i<=n;i++)
{
add2(edge[i],i);
}
//check();
}
void resh()
{
int seg=0;
for(int i=1;i<=k;i++)
{
if(!used[i])
{
add3(edge[edge1[i].in]);
}
}
for(int i=1;i<=k;i++)
{
for(int j=1;j<=k;j++)
{
if(used[j])
{
int l1=get_lead(edge1[j].a);
int l2=get_lead(edge1[j].b);
if(l1!=l2)
{
if(has1[l2])swap(l1,l2);
if(has1[l1])
{
has1[l2]=1;
nhas1.push_back(l2);
mult[l2]+=mult[l1]+edge1[j].c;
seg+=mult[l2]*val[l2];
used[j]=0;
}
}
}
}
}
while(nhas1.size()!=0)
{
has1[nhas1[nhas1.size()]]=0;
mult[nhas1[nhas1.size()]]=0;
nhas1.pop_back();
}
for(int i=1;i<=k;i++)rem();
otg=max(otg,seg);
}
void rec()
{
for(int i=1;i<(1<<k);i++)
{
int in=i;
for(int j=20;j>=0;j--)
{
if(in>=(1<<j))
{
used[j+1]=1;
in-=(1<<j);
}
}
resh();
}
}
void read()
{
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
cin>>edge[i].a>>edge[i].b>>edge[i].c;
}
for(int i=1;i<=k;i++)
{
cin>>edge1[i].a>>edge1[i].b;
}
for(int i=1;i<=n;i++)
{
cin>>br[i];
}
sort(edge+1,edge+m+1,cmp);
find_c();
addperm();
rec();
cout<<otg<<endl;
}
int main()
{
speed();
read();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
