Submission #1263668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263668		denislav	Bridges (APIO19_bridges)	C++20	59 / 100	3094 ms	13656 KiB

bridges

# include <iostream>
# include <vector>
# include <unordered_set>
# include <unordered_map>
# include <algorithm>
using namespace std;

const int MAX=1e5+11,S=333;

int n,m,q;
pair<int,int> edges[MAX];
int edgeW[MAX];

int ct;
struct Change
{
    int tm,*ptr,last_val;
};

vector<Change> changes;
int sz[MAX];
int par[MAX];

void init()
{
    ct=0;
    changes.clear();
    for(int i=1;i<=n;i++)
    {
        sz[i]=1;
        par[i]=i;
    }
}

int root(int u)
{
    if(par[u]==u) return u;
    else return root(par[u]);
}

void unite(int u, int v)
{
    //cout<<"+"<<u<<" "<<v<<endl;

    ct++;
    u=root(u);
    v=root(v);
    if(u==v) return ;

    if(sz[u]<sz[v]) swap(u,v);
    changes.push_back({ct,par+v,v});
    changes.push_back({ct,sz+u,sz[u]});

    par[v]=u;
    sz[u]+=sz[v];
}

void rollback()
{
    ct--;
    while(changes.size()>0 and changes.back().tm>ct)
    {
        int *ptr=changes.back().ptr,last_val=changes.back().last_val;
        (*ptr)=last_val;
        changes.pop_back();
    }
}

struct Query
{
    int type,id,w;
}z[MAX];

unordered_map<int,int> mp[S];
int out[MAX];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v>>edgeW[i];
        edges[i]={u,v};
    }

    cin>>q;
    int last_query=0;
    for(int tt=1;tt<=q;tt++)
    {
        cin>>z[tt].type>>z[tt].id>>z[tt].w;
        if(!(tt%S==0 or tt==q)) continue;

        int l=last_query+1,r=tt;
        last_query=tt;

        unordered_set<int> all;
        for(int i=1;i<=m;i++) all.insert(i);
        unordered_map<int,int> curr;
        for(int i=l;i<=r;i++)
        {
            if(z[i].type==1)
            {
                int x=z[i].id;
                if(all.find(x)!=all.end())
                {
                    all.erase(x);
                    curr[x]=edgeW[x];
                }
            }
        }

        vector<pair<int,int>> before,now;
        for(int x: all) before.push_back({edgeW[x],x});

        for(int i=l;i<=r;i++)
        {
            if(z[i].type==1) continue;
            mp[i%S]=curr;
            for(int j=l;j<i;j++)
            {
                if(z[j].type==1)
                {
                    mp[i%S][z[j].id]=z[j].w;
                }
            }

            now.push_back({z[i].w,i});
        }

        init();
        sort(before.rbegin(),before.rend());
        sort(now.rbegin(),now.rend());
        int ptr=0;
        for(int i=0;i<(int)now.size();i++)
        {
            int idx=now[i].second;
            while(ptr<(int)before.size() and before[ptr].first>=z[idx].w)
            {
                unite(edges[before[ptr].second].first,edges[before[ptr].second].second);
                ptr++;
            }

            //cout<<idx<<":"<<"\n";
            for(pair<int,int> pa: mp[idx%S])
            {
                //cout<<pa.first<<" "<<pa.second<<"\n";
                if(pa.second>=z[idx].w)
                {
                    unite(edges[pa.first].first,edges[pa.first].second);
                }
            }
            //cout<<"\n";
            out[idx]=sz[root(z[idx].id)];
            for(pair<int,int> pa: mp[idx%S])
            {
                if(pa.second>=z[idx].w)
                {
                    //cout<<"-"<<"\n";
                    rollback();
                }
            }
        }

        for(int i=l;i<=r;i++)
        {
            if(z[i].type==1) edgeW[z[i].id]=z[i].w;
        }
    }

    for(int i=1;i<=q;i++)
    {
        if(z[i].type==2) cout<<out[i]<<"\n";
    }

    return 0;
}

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