Submission #1106221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106221		vivkostov	Toll (APIO13_toll)	C++14	0 / 100	1 ms	6480 KiB

toll

#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
{
    long long int a,b,c,in;
};
bool cmp(cell a1,cell a2)
{
    return a1.c<a2.c;
}
long long int n,m,k,br[100005],sz[100005],lead[100005],used[30],val[100005],has1[100005],otg,mult[100005];
vector<long long int>nhas1;
cell edge[300005],edge1[300005];
stack<cell>s;
void prec()
{
    has1[1]=1;
    for(long long int i=1;i<=n;i++)
    {
        lead[i]=i;
        sz[i]=1;
        val[i]=br[i];
    }
}
long long int get_lead(long long int beg)
{
    if(lead[beg]==beg)return beg;
    return get_lead(lead[beg]);
}
void add(cell ed)
{
    long long int a=ed.a,b=ed.b;
    long long int la=get_lead(a),lb=get_lead(b);
    if(la==lb)return;
    for(long long int i=1;i<=k;i++)
    {
        long long 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,long long int in)
{
    long long int a=ed.a,b=ed.b;
    long long int la=get_lead(a),lb=get_lead(b);
    if(la==lb)return;
    for(long long int i=1;i<=k;i++)
    {
        long long 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)
{
    long long int a=ed.a,b=ed.b;
    long long 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()
{
    long long 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(long long int i=1;i<=m;i++)
    {
        add(edge[i]);
    }
    prec();
}
void check()
{
    for(long long int i=1;i<=n;i++)
    {
        cout<<i<<" "<<lead[i]<<" "<<sz[i]<<" "<<has1[i]<<endl;
    }
    cout<<endl;
}
void addperm()
{
    for(long long int i=1;i<=n;i++)
    {
        add2(edge[i],i);
    }
    check();
}
void resh()
{
    long long int seg=0;
    for(long long int i=1;i<=k;i++)
    {
        if(!used[i])
        {
            add3(edge[edge1[i].in]);
        }
    }
    cout<<1<<endl;
    check();
    for(long long int i=1;i<=k;i++)
    {
        for(long long int j=1;j<=k;j++)
        {
            if(used[j])
            {
                long long int l1=get_lead(edge1[j].a);
                long long 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(long long int i=1;i<=k;i++)rem();
    otg=max(otg,seg);
}
void rec()
{
    for(long long int i=0;i<(1<<k);i++)
    {
        long long int in=i;
        for(long long 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(long long int i=1;i<=m;i++)
    {
        cin>>edge[i].a>>edge[i].b>>edge[i].c;
    }
    for(long long int i=1;i<=k;i++)
    {
        cin>>edge1[i].a>>edge1[i].b;
    }
    for(long long 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;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22