Submission #1109348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109348		vivkostov	Toll (APIO13_toll)	C++14	16 / 100	45 ms	17652 KiB

toll

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const long long int inf=2000000000000000001;
struct cell
{
    long long int to,st;
};
struct poin
{
    long long int a,b,c;
};
bool cmp(poin a1,poin a2)
{
    return a1.c<a2.c;
}
long long int n,m,k,br[100005],l[100],r[100],used[100005],lead[100005],sz[100005],num[100005],use[100005],basic_lead[100005],numb,group[200005];
long long int otg[2000005],dpmi[200005],dpbr[200005],used1[100005];
poin f[300005];
vector<cell>v[100005];
vector<cell>vert[100005];
stack<pair<int,int>>s;
void prec()
{
    for(int i=1;i<=n;i++)
    {
        lead[i]=i;
        sz[i]=1;
        num[i]=br[i];
    }
}
int get_lead(int beg)
{
    if(beg==lead[beg])return beg;
    return lead[beg]=get_lead(lead[beg]);
}
int get_lead2(int beg)
{
    if(beg==lead[beg])return beg;
    return get_lead2(lead[beg]);
}
void add1(int a,int b)
{
    a=get_lead(a);
    b=get_lead(b);
    if(a==b||(used[a]&&used[b]))return;
    if(sz[a]<sz[b])swap(a,b);
    if(used[b])used[a]=1;
    lead[b]=a;
    sz[a]+=sz[b];
    num[a]+=num[b];
}
void add2(int a,int b)
{
    a=get_lead2(a);
    b=get_lead2(b);
    if(sz[a]<sz[b])swap(a,b);
    lead[b]=a;
    sz[a]+=sz[b];
    num[a]+=num[b];
    pair<int,int>p;
    p.first=a;
    p.second=b;
    s.push(p);
}
void rem(int brx)
{
    int a,b;
    for(int i=1;i<=brx;i++)
    {
        a=s.top().first,b=s.top().second;
        sz[a]-=sz[b];
        num[a]-=num[b];
        lead[b]=b;
        s.pop();
    }
}
void get_basic()
{
    memset(used,0,sizeof(used));
    int l;
    for(int i=1;i<=n;i++)
    {
        l=get_lead(i);
        if(!used[l])
        {
            used[l]=1;
            numb++;
            basic_lead[numb]=l;
        }
    }
}
void Clear()
{
    int w;
    for(int i=1;i<=numb;i++)
    {
        w=basic_lead[i];
        v[w].clear();
        dpbr[w]=0;
        dpmi[w]=inf;
    }
    memset(used1,0,sizeof(used1));
}
void get_group()
{
    for(int i=1;i<=n;i++)
    {
        group[i]=get_lead(i);
    }
}
void fill_vert()
{
    int w1,w2,brx=0;
    cell h;
    for(int i=1;i<=m;i++)
    {
        w1=group[f[i].a];
        w2=group[f[i].b];
        if(get_lead2(w1)!=get_lead2(w2))
        {
            h.to=w2;
            h.st=f[i].c;
            vert[w1].push_back(h);
            h.to=w1;
            vert[w2].push_back(h);
            add2(w1,w2);
            brx++;
        }
    }
    rem(brx);
    /*cout<<numb<<endl;
    for(int i=1;i<=numb;i++)
    {
        cout<<basic_lead[i]<<endl;
        for(int j=0;j<vert[basic_lead[i]].size();j++)
        {
            cout<<vert[basic_lead[i]][j].to<<" "<<vert[basic_lead[i]][j].st<<endl;
        }
        cout<<endl;
    }
    cout<<endl;
    */
}
long long int dfs1(int beg,int p)
{
    long long int sum=0,w;
    dpbr[beg]=num[beg];
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i].to;
        if(w!=p)
        {
            sum+=dfs1(w,beg);
            dpbr[beg]+=dpbr[w];
            dpmi[beg]=min(dpmi[beg],dpmi[w]);
            if(v[beg][i].st==-1)
            {
                sum+=dpbr[w]*dpmi[w];
            }
        }
        if(beg==1)memset(used1,0,sizeof(used1));
    }
    for(int i=0;i<vert[beg].size();i++)
    {
        if(!used1[vert[beg][i].to])
        {
            dpmi[beg]=min(dpmi[beg],vert[beg][i].st);
        }
    }
    //cout<<dpbr[beg]<<" "<<dpmi[beg]<<" "<<beg<<" "<<sum<<endl;
    used1[beg]=1;
    return sum;
}
void calc(int ind)
{
    int w1,w2,brx=0;
    cell h;
    for(int i=1;i<=k;i++)
    {
        if(use[i])
        {
            w1=get_lead2(l[i]);
            w2=get_lead2(r[i]);
            if(w1!=w2)
            {
                h.to=group[r[i]];
                h.st=-1;
                v[group[l[i]]].push_back(h);
                h.to=group[l[i]];
                v[group[r[i]]].push_back(h);
                add2(w1,w2);
                brx++;
            }
        }
    }
    int bl1,bl2;
    //cout<<numb<<endl;
    for(int i=1;i<=numb;i++)
    {
        bl1=basic_lead[i];
        for(int j=0;j<vert[bl1].size();j++)
        {
            bl2=vert[bl1][j].to;
            w1=get_lead2(bl1);
            w2=get_lead2(bl2);
            if(w1!=w2)
            {
                h.to=bl2;
                h.st=vert[bl1][j].st;
                v[bl1].push_back(h);
                h.to=bl1;
                v[bl2].push_back(h);
                add2(w1,w2);
                brx++;
            }
        }
    }
    rem(brx);
    otg[ind]=dfs1(group[1],0);
    /*cout<<endl;
    cout<<ind<<endl;
    for(int i=1;i<=numb;i++)
    {
        cout<<basic_lead[i]<<endl;
        for(int j=0;j<v[basic_lead[i]].size();j++)
        {
            cout<<v[basic_lead[i]][j].to<<" "<<v[basic_lead[i]][j].st<<endl;
        }
        cout<<endl;
    }
    cout<<endl;
    */
    Clear();
}
void rec()
{
    for(int i=0;i<(1<<k);i++)
    {
        int fi=i*2;
        for(int j=k;j>=1;j--)
        {
            if(fi>=(1<<j))
            {
                fi-=(1<<j);
                use[j]=1;
            }
        }
        calc(i);
        for(int j=1;j<=k;j++)use[j]=0;
    }
}
void read()
{
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        cin>>f[i].a>>f[i].b>>f[i].c;
    }
    for(int i=1;i<=k;i++)
    {
        cin>>l[i]>>r[i];
        used[l[i]]=1;
        used[r[i]]=1;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>br[i];
    }
    prec();
    sort(f+1,f+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        add1(f[i].a,f[i].b);
    }
    get_basic();
    get_group();
    fill_vert();
    Clear();
    rec();
    long long int motg=0;
    for(int i=1;i<(1<<k);i++)
    {
        motg=max(motg,otg[i]);
    }
    cout<<motg<<endl;
}
int main()
{
    speed();
    read();
    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 (stderr)

toll.cpp: In function 'long long int dfs1(int, int)':
toll.cpp:155:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
toll.cpp:170:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |     for(int i=0;i<vert[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~
toll.cpp: In function 'void calc(int)':
toll.cpp:208:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  208 |         for(int j=0;j<vert[bl1].size();j++)
      |                     ~^~~~~~~~~~~~~~~~~

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