Submission #480453

#	Time	Username	Problem	Language	Result	Execution time	Memory
480453		oneloveforever	Toll (APIO13_toll)	C++14	56 / 100	2564 ms	21520 KiB

toll

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define x first
#define y second
#define ii pair<int,int>
int n,m,k;
vector<vector<int> >a;
const int M=1e5+7;
const int inf=1e9+7;
int num_child[M],trace[M],l[M];
struct DSU
{
    vector<int>sz,trace;
    int n;
    DSU(int _n=0)
    {
        n=_n;
        sz.assign(n+7,1);
        trace.resize(n+7);
        iota(trace.begin(),trace.end(),0);
    }
    int get_dsu(int x)
    {
        return trace[x]==x?x:(trace[x]=get_dsu(trace[x]));
    }
    bool check(int x,int y)
    {
        int u=get_dsu(x);
        int v=get_dsu(y);
        return u==v;
    }
    bool get(int x,int y)
    {
        int u=get_dsu(x);
        int v=get_dsu(y);
        if(u==v)return true;
        if(sz[u]>sz[v])swap(u,v);
        trace[u]=v;
        sz[v]+=sz[u];
        return false;
    }
};
struct node
{
    int x,y,cost;
    node(int _x=0,int _y=0,int _cost=0)
    {
        x=_x,y=_y,cost=_cost;
    }
    bool operator<(const node &a)const
    {
        return cost<a.cost;
    }
};
void dfs(int x,int cha)
{
    trace[x]=cha;
    l[x]=l[cha]+1;
    for(auto node:a[x])
    {
        if(node!=cha)
        {
            dfs(node,x);
            num_child[x]+=num_child[node];
        }
    }
}
int get_bit(int x,int y)
{
    return x&(1<<y);
}
bool maximize(ll &a,ll b)
{
    if(a<b)
    {
        a=b;
        return true;
    }
    return false;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    vector<node>e;
    vector<int>color(n+1);
    for(int i=1;i<=m;i++)
    {
        int x,y,cost;
        cin>>x>>y>>cost;
        e.push_back({x,y,cost});
    }
    vector<node>mst;
    sort(e.begin(),e.end());
    DSU s(n);
    for(auto node:e)
    {
        if(!s.check(node.x,node.y))
        {
            mst.push_back({node.x,node.y,node.cost});
        }
    }
    s=DSU(n);
    vector<ii>edge;
    for(int i=1;i<=k;i++)
    {
        int x,y;
        cin>>x>>y;
        edge.push_back(make_pair(x,y));
        s.get(x,y);
    }
    vector<node>need,basic;
    for(auto node:mst)
    {
        if(!s.get(node.x,node.y))
        {
            need.push_back({node.x,node.y,node.cost});
        }
        else basic.push_back({node.x,node.y,node.cost});
    }
    for(int i=1;i<=n;i++)
    {
        cin>>color[i];
    }
    s=DSU(n);
    for(auto node:need)
    {
        s.get(node.x,node.y);
    }
    vector<int>index(n+1);
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(s.get_dsu(i)!=i)continue;
        index[i]=++cnt;
    }
    for(int i=1;i<=n;i++)
    {
        index[i]=index[s.get_dsu(i)];
    }
    vector<int>sum(cnt+1,0);
    for(int i=1;i<=n;i++)
    {
        sum[index[i]]+=color[i];
    }
    a.resize(cnt+7);
    int sz=(int)basic.size();
    ll kq=0;
    for(int mask=0;mask<(1<<k);mask++)
    {
        bool check=true;
        s=DSU(cnt);
        vector<bool>check_edge(sz,false);
        for(int i=1;i<=cnt;i++)
        {
            a[i].clear();
            num_child[i]=sum[i];
        }
        for(int i=0;i<k;i++)
        {
            if(!get_bit(mask,i))continue;
            ii res=edge[i];
            int u=index[res.x];
            int v=index[res.y];
            if(s.check(u,v))
            {
                check=false;
                break;
            }
            s.get(u,v);
            //cout<<u<<" "<<v<<"-----"<<endl;
            a[u].push_back(v);
            a[v].push_back(u);
        }
        if(!check)continue;
        for(int i=0;i<sz;i++)
        {
            node res=basic[i];
            int u=index[res.x];
            int v=index[res.y];
            if(s.check(u,v))continue;
            else
            {
                s.get(u,v);
                check_edge[i]=true;
                a[u].push_back(v);
                a[v].push_back(u);
            }
        }
        //cout<<mask<<endl;
        dfs(index[1],0);
        vector<int>cp(sz+1);
        for(int i=0;i<k;i++)
        {
            if(!get_bit(mask,i))continue;
            ii node=edge[i];
            int u=index[node.x];
            int v=index[node.y];
            if(trace[v]==u)swap(u,v);
            cp[u]=inf;
        }
        for(int i=0;i<sz;i++)
        {
            if(!check_edge[i])continue;
            node res=basic[i];
            int u=index[res.x];
            int v=index[res.y];
            if(trace[v]==u)swap(u,v);
            cp[u]=0;
        }
        for(int i=0;i<sz;i++)
        {
            if(check_edge[i])continue;
            node res=basic[i];
            int u=index[res.x];
            int v=index[res.y];
            if(l[u]>l[v])swap(u,v);
            int cost=res.cost;
            while(l[v]>l[u])
            {
                cp[v]=min(cp[v],cost);
                v=trace[v];
            }
            while(v!=u)
            {
                cp[u]=min(cp[u],cost);
                cp[v]=min(cp[v],cost);
                u=trace[u];
                v=trace[v];
            }
        }
        ll ans=0;
        for(int i=1;i<=cnt;i++)
        {
            ans+=1LL*cp[i]*num_child[i];
        }
        maximize(kq,ans);
    }
    cout<<kq;
}

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