Submission #1108729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108729		vivkostov	Toll (APIO13_toll)	C++14	16 / 100	4 ms	19024 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],par[200005],parto[100005],dpmi[200005],dpbr[200005],used1[100];
cell mi[100005];
poin f[300005];
vector<cell>v[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];
    }
    for(int i=1;i<=n;i++)
    {
        mi[i].st=inf;
    }
}
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_min_vertex()
{
    int a1,a2;
    for(int i=1;i<=m;i++)
    {
        a1=get_lead(f[i].a);
        a2=get_lead(f[i].b);
        if(a1!=a2)
        {
            if(mi[a1].st>f[i].c)
            {
                mi[a1].st=f[i].c;
                mi[a1].to=a2;
            }
            if(mi[a2].st>f[i].c)
            {
                mi[a2].st=f[i].c;
                mi[a2].to=a1;
            }
        }
    }
}
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 dfs(int beg,int p)
{
    int w;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i].to;
        if(w!=p)
        {
            par[w]=v[beg][i].st;
            parto[w]=beg;
            dfs(w,beg);
        }
    }
}
void Clear()
{
    int w;
    for(int i=1;i<=numb;i++)
    {
        w=basic_lead[i];
        v[w].clear();
        dpbr[w]=0;
        dpmi[w]=inf;
    }
}
void get_par()
{
    int w,brx=0;
    cell h;
    for(int i=1;i<=numb;i++)
    {
        w=basic_lead[i];
        if(get_lead2(w)!=get_lead2(mi[w].to))
        {
            add2(w,mi[w].to);
            h.to=w;
            h.st=mi[w].st;
            v[w].push_back(mi[w]);
            v[mi[w].to].push_back(h);
            brx++;
        }
    }
    dfs(group[1],0);
    rem(brx);
    Clear();
    /*for(int i=1;i<=numb;i++)
    {
        w=basic_lead[i];
        cout<<w<<endl;
        for(int j=0;j<v[w].size();j++)
        {
            cout<<v[w][j].to<<" "<<v[w][j].st<<endl;
        }
        cout<<endl;
    }
    */
}
long long int dfs1(int beg,int p)
{
    int w;
    long long int sum=0;
    if(parto[beg]!=p)dpmi[beg]=par[beg];
    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);
            if(v[beg][i].st==-1)
            {
                sum+=min(dpmi[w],par[w])*dpbr[w];
            }
            dpmi[beg]=min(dpmi[beg],dpmi[w]);
            dpbr[beg]+=dpbr[w];
        }
    }
    //cout<<beg<<" "<<dpmi[beg]<<" "<<dpbr[beg]<<" "<<sum<<endl;
    return sum;
}
void calc(int ind)
{
    int w1,w2,brx=0;
    cell h;
    for(int i=1;i<=k;i++)
    {
        if(use[i])
        {
            w1=group[l[i]];
            w2=group[r[i]];
            if(get_lead2(w1)!=get_lead2(w2))
            {
                h.to=w2;
                h.st=-1;
                v[w1].push_back(h);
                h.to=w1;
                v[w2].push_back(h);
                add2(w1,w2);
                brx++;
            }
        }
    }
    for(int i=1;i<=numb;i++)
    {
        w1=basic_lead[i];
        if(get_lead2(w1)!=get_lead2(mi[w1].to))
        {
            add2(w1,mi[w1].to);
            h.to=w1;
            h.st=mi[w1].st;
            v[w1].push_back(mi[w1]);
            v[mi[w1].to].push_back(h);
            brx++;
        }
    }
    rem(brx);
    otg[ind]=dfs1(group[1],0);
    /*cout<<ind<<endl;
    for(int i=1;i<=numb;i++)
    {
        w1=basic_lead[i];
        cout<<w1<<endl;
        for(int j=0;j<v[w1].size();j++)
        {
            cout<<v[w1][j].to<<" "<<v[w1][j].st<<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 get_group()
{
    for(int i=1;i<=n;i++)
    {
        group[i]=get_lead(i);
    }
}
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_min_vertex();
    get_basic();
    get_group();
    get_par();
    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 'void dfs(int, int)':
toll.cpp:128:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
toll.cpp: In function 'long long int dfs1(int, int)':
toll.cpp:188:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~

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