Submission #480726

#	Time	Username	Problem	Language	Result	Execution time	Memory
480726		oneloveforever	Bridges (APIO19_bridges)	C++11	100 / 100	2736 ms	9612 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<int> >a;
int n,m,t;
struct edge
{
    int x,y,cost;
    edge(int _x=0,int _y=0,int _cost=0)
    {
        x=_x,y=_y,cost=_cost;
    }
};
struct query
{
    int type,x,y;
    query(int _type=0,int _x=0,int _y=0)
    {
        type=_type,x=_x,y=_y;
    }
};
struct DSU
{
    int n;
    vector<int>trace,sz,roll;
    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?x:find_dsu(trace[x]);
    }
    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];
        roll.push_back(u);
    }
    void rollback(int x)
    {
        while((int)roll.size()>x)
        {
            int new_node=roll.back();
            sz[trace[new_node]]-=sz[new_node];
            trace[new_node]=new_node;
            roll.pop_back();
        }
    }
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    vector<edge>a(m+1);
    for(int i=1;i<=m;i++)
    {
        int x,y,cost;
        cin>>x>>y>>cost;
        a[i]={x,y,cost};
    }
    cin>>t;
    vector<query>q(t+1);
    for(int i=1;i<=t;i++)
    {
        int type,x,y;
        cin>>type>>x>>y;
        q[i]={type,x,y};
    }
    int sz_block=1000;
    vector<int>ans(t+1);
    for(int i=1;i<=t;i+=sz_block)
    {
        int val_x=i;
        int val_y=min(t,i+sz_block-1);
        DSU dsu(n);
        vector<int>up,answer,pre;
        vector<bool>check_edge(m+1,false);
        for(int i=val_x;i<=val_y;i++)
        {
            if(q[i].type==1)
            {
                check_edge[q[i].x]=true;
                up.push_back(i);
            }
            else answer.push_back(i);
        }
        for(int i=1;i<=m;i++)
        {
            if(check_edge[i])continue;
            pre.push_back(i);
        }
        vector<vector<int> >block(sz_block+1);
        for(int i=val_x;i<=val_y;i++)
        {
            if(q[i].type==1)a[q[i].x].cost=q[i].y;
            else
            {
                //cout<<i<<" "<<q[i].y<<endl;
                for(auto node:up)
                {
                  //  cout<<a[q[node].x].cost<<endl;
                    if(a[q[node].x].cost>=q[i].y)block[i-val_x].push_back(node);
                }
            }
        }
        sort(pre.begin(),pre.end(),[&](int x,int y){return a[x].cost>a[y].cost;});
        sort(answer.begin(),answer.end(),[&](int x,int y){return q[x].y>q[y].y;});
        int vt=0;
        for(auto node:answer)
        {
            int new_node=q[node].x;
            int cost=q[node].y;
            while(vt<(int)pre.size()&&a[pre[vt]].cost>=cost)
            {
                dsu.get(a[pre[vt]].x,a[pre[vt]].y);
                ++vt;
            }
            int need=dsu.roll.size();
            for(auto res:block[node-val_x])
            {
                dsu.get(a[q[res].x].x,a[q[res].x].y);
            }
            int pre_sz=dsu.sz[dsu.find_dsu(new_node)];
            ans[node]=pre_sz;
            dsu.rollback(need);
        }

    }
    for(int i=1;i<=t;i++)
    {
        if(q[i].type==1)continue;
        cout<<ans[i]<<endl;
    }
}

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27