Submission #490858

#	Time	Username	Problem	Language	Result	Execution time	Memory
490858		oneloveforever	Toll (APIO13_toll)	C++14	0 / 100	1 ms	204 KiB

toll

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define x first
#define y second
#define ii pair<int,int>
const int inf=1e9+7;
const int M=1e4+7;
int high[M],trace[M],cost[M];
vector<vector<ii> >used;
struct node
{
    int x,y,cost;
    bool check=false,need=false;
    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;
    }
};
struct DSU
{
    int n;
    vector<int>trace,sz;
    DSU(int _n=0)
    {
        n=_n;
        trace.resize(n+7);
        sz.assign(n+7,1);
        iota(trace.begin(),trace.end(),0);
    }
    int find_dsu(int x)
    {
        return trace[x]==x?trace[x]:find_dsu(trace[x]);
    }
    bool check(int x,int y)
    {
        return find_dsu(x)==find_dsu(y);
    }
    void get(int x,int y)
    {
        int u=find_dsu(x);
        int v=find_dsu(y);
        if(u==v)return ;
        if(sz[u]>sz[v])swap(u,v);
        trace[u]=v;
        sz[v]+=sz[u];
    }
    void re()
    {
        for(int i=1;i<=n;i++)trace[i]=i;
    }
};
int n,m,k;
void dfs(int x,int cha)
{
    for(ii u:used[x])
    {
        int node=u.x;
        int value=u.y;
        if(node==cha)continue;
        high[node]=high[x]+1;
        cost[node]=value;
        trace[node]=x;
        dfs(node,x);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    vector<node>edge(m+1);
    for(int i=1;i<=m;i++)
    {
        int x,y,cost;
        cin>>x>>y>>cost;
        edge[i]={x,y,cost};
    }
    sort(edge.begin(),edge.end());
    vector<ii>a(k+1);
    for(int i=1;i<=k;i++)
    {
        int x,y;
        cin>>x>>y;
        a[i]=make_pair(x,y);
    }
    DSU s(n);
    vector<int>color(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>color[i];
    }
    for(int i=1;i<=m;i++)
    {
        if(!s.check(edge[i].x,edge[i].y))
        {
            edge[i].check=true;
            s.get(edge[i].x,edge[i].y);
        }
    }
    s.re();
    for(int i=1;i<=k;i++)
    {
        if(!s.check(a[i].x,a[i].y))
        {
            s.get(a[i].x,a[i].y);
        }
    }
    vector<int>save;
    for(int i=1;i<=m;i++)
    {
        if(!s.check(edge[i].x,edge[i].y))
        {
            s.get(edge[i].x,edge[i].y);
            edge[i].need=true;
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(edge[i].check&&!edge[i].need)
        {
            save.push_back(i);
        }
    }
    s.re();
    for(int i=1;i<=m;i++)
    {
        if(edge[i].need)
        {
            s.get(edge[i].x,edge[i].y);
        }
    }
    int num_color=0;
    vector<int>value(n+1);
    for(int i=1;i<=n;i++)
    {
        if(s.find_dsu(i)!=i)continue;
        value[i]=++num_color;
    }
    vector<int>num_child(num_color+1);
    for(int i=1;i<=n;i++)
    {
        int x=s.find_dsu(i);
        num_child[value[x]]+=color[i];
    }

    for(int i=1;i<=k;i++)
    {
        int x=s.find_dsu(a[i].x);
        int y=s.find_dsu(a[i].y);
        a[i].x=value[x];
        a[i].y=value[y];
    }
    for(int node:save)
    {
        int x=s.find_dsu(edge[node].x);
        int y=s.find_dsu(edge[node].y);
        edge[node].x=value[x];
        edge[node].y=value[y];
    }
    DSU dsu(num_color);
    used.resize(num_color+1);
    int ans=0;
    for(int mask=0;mask<(1<<k);mask++)
    {
        dsu.re();
        for(int i=1;i<=num_color;i++)used.clear();
        for(int i=1;i<=num_color;i++)high[i]=0;
        bool check=false;
        for(int i=1;i<=k;i++)
        {
            if(!((mask>>(i-1))&1))continue;
            if(dsu.check(a[i].x,a[i].y))check=true;
            dsu.get(a[i].x,a[i].y);
            used[a[i].x].push_back({a[i].y,inf});
            used[a[i].y].push_back({a[i].x,inf});
        }
        if(check)continue;
        vector<int>solve;
        for(int node:save)
        {
            int x=edge[node].x;
            int y=edge[node].y;
            if(dsu.check(x,y))
            {
                solve.push_back(node);
                continue;
            }
            dsu.check(x,y);
            used[x].push_back({y,0});
            used[y].push_back({x,0});
        }
        dfs(1,0);

        for(int node:solve)
        {
            int x=edge[node].x;
            int y=edge[node].y;
            int value=edge[node].cost;
            if(high[x]>high[y])swap(x,y);
            while(high[y]>high[x])
            {
                cost[y]=min(cost[y],value);
                y=trace[y];
            }
            while(x!=y)
            {
                cost[x]=min(cost[x],value);
                cost[y]=min(cost[y],value);
                x=trace[x];
                y=trace[y];
            }
        }
        int sum=0;
        for(int i=2;i<=num_color;i++)
        {
            sum+=cost[i]*num_child[i];
        }
        ans=max(ans,sum);
    }
    cout<<ans;


}

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