제출 #480484

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
480484		oneloveforever	통행료 (APIO13_toll)	C++14	16 / 100	2575 ms	11652 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;
const int LOG=19;
int num_child[M],trace[M][LOG+10],l[M],fin[M],beg[M],num_node;
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)
{
    beg[x]=++num_node;
    //cout<<x<<endl;
    for(auto node:a[x])
    {
        if(node!=cha)
        {
            trace[node][0]=x;
            l[node]=l[x]+1;
            dfs(node,x);
            num_child[x]+=num_child[node];
        }
    }
    fin[x]=num_node;
}
void sprase(int n)
{
    for(int i=1; i<=LOG; i++)
    {
        for(int node=1; node<=n; node++)
        {
            if(trace[node][i]!=-1)
            {
                trace[node][i]=trace[trace[node][i-1]][i-1];
            }
        }
    }
}
int lca(int x,int y)
{
    if(l[x]>l[y])swap(x,y);
    int value=l[y]-l[x];
    for(int i=LOG-1; i>=0; i--)
    {
        if(value&(1<<i))y=trace[y][i];
    }
    if(x==y)return x;
    for(int i=LOG-1; i>=0; i--)
    {
        if(trace[x][i]!=trace[y][i])
        {
            x=trace[x][i];
            y=trace[y][i];
        }
    }
}
struct BIT
{
    vector<int>bit;
    int n;
    BIT(int _n=0)
    {
        n=_n;
        bit.assign(n+7,0);
    }
    void update(int x,int value)
    {
        for(; x<=n; x+=x&(-x))
        {
            bit[x]+=value;
        }
    }
    int get_sum(int x)
    {
        int ans=0;
        for(;x;x-=x&(-x))
        {
            ans+=bit[x];
        }
        return ans;
    }
    void up(int x,int y,int value)
    {
        update(x,value);
        if(y+1<=n)
        {
            update(y+1,-value);
        }
    }

};
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;
}
BIT tree;
int jump(int x)
{
    int value=tree.get_sum(beg[x]);

    for(int i=LOG-1; i>=0; i--)
    {
        //cout<<i<<" "<<trace[x][i]<<endl;
        if(trace[x][i]==-1)continue;
        if(tree.get_sum(trace[x][i])==value)
        {
            x=trace[x][i];
        }
    }
    return x;
}
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.get(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);
        memset(trace,-1,sizeof(trace));
        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;
        num_node=0;
        dfs(index[1],0);
        //cout<<num_node<<endl;
        sprase(cnt);
        tree=BIT(cnt);
        for(int i=2; i<=cnt; i++)
        {
            //cout<<beg[i]<<" "<<fin[i]<<endl;
            tree.up(beg[i],fin[i],1);
        }

        vector<int>cp(cnt+1);

        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][0]==u)swap(u,v);
            tree.up(beg[u],fin[u],-1);
            cp[u]=0;
        }

//        cout<<lca(1,2)<<endl;;
        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];
            int new_lca=lca(u,v);
            int cost=res.cost;
            //cout<<u<<" "<<v<<" "<<new_lca<<" "<<mask<<endl;
            for(u=jump(u);l[u]>l[new_lca]; u=jump(u))
            {
                //cout<<u<<endl;
                cp[u]=cost;
                tree.up(beg[u],fin[u],-1);
            }
            for(v=jump(v);l[v]>l[new_lca];v=jump(v))
            {
                cp[v]=cost;
                tree.up(beg[v],fin[v],-1);
            }
        }
        ll ans=0;
        for(int i=1; i<=cnt; i++)
        {
            ans+=1LL*cp[i]*num_child[i];
        }
        maximize(kq,ans);
    }
    cout<<kq;
}

컴파일 시 표준 에러 (stderr) 메시지

toll.cpp: In function 'int lca(int, int)':
toll.cpp:103:1: warning: control reaches end of non-void function [-Wreturn-type]
  103 | }
      | ^

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