Submission #981306

#	Time	Username	Problem	Language	Result	Execution time	Memory
981306		Kenjikrab	Bridges (APIO19_bridges)	C++14	100 / 100	1856 ms	10816 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
int const n_max=5e4+100;
int const sq=750;

int n,m,q;
int u[2*n_max],v[2*n_max],d[2*n_max];
int t[2*n_max],s[2*n_max],w[2*n_max],ans[2*n_max];
int p[n_max],sz[n_max];
bool changed[2*n_max];
vector<int> tojoin[sq+100];
stack<int> stk;
void reset()
{
    iota(p+1,p+n+1,1);
    fill(sz+1,sz+n+1,1);
    fill(changed+1,changed+m+1,false);
    while(!stk.empty())stk.pop();
}
int find_p(int a)
{
    if(p[a]==a)return a;
    return find_p(p[a]);
}
int combine(int a,int b)
{
    a=find_p(a),b=find_p(b);
    if(sz[a]<sz[b])swap(a,b);
    //cout<<"COM"<<" "<<a<<" "<<b<<endl;
    if(a==b)return 0;
    sz[a]+=sz[b];
    p[b]=a;
    return b;
}
void roll_back(int a)
{
    while(stk.size()>a)
    {
        int x=stk.top();
        stk.pop();
        if(x==0)continue;
        sz[find_p(x)]-=sz[x];
        p[x]=x;
        //cout<<"DEL "<<x<<endl;
    }
}
signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u[i]>>v[i]>>d[i];
    }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>t[i]>>s[i]>>w[i];
    }
    
    for(int l=1;l<=q;l+=sq)
    {
        int r=min(l+sq-1,q);
        //cout<<l<<"&"<<r<<endl;
        reset();
        vector<int> ask,upd;
        vector<int> unchanged;
        for(int i=l;i<=r;i++)
        {
            if(t[i]==1)
            {
                upd.push_back(i);
                changed[s[i]]=true;
            }
            else
            {
                ask.push_back(i);
            }
        }
        for(int i=l;i<=r;i++)
        {
            if(t[i]==1)
            {
                d[s[i]]=w[i];
            }
            else
            {
                tojoin[i-l].clear();
                for(auto it:upd)
                {
                    if(d[s[it]]>=w[i])
                    {
                        tojoin[i-l].push_back(s[it]);
                    }
                }
            }
        }
        for(int i=1;i<=m;i++)if(!changed[i])unchanged.push_back(i);
        //for(auto it:unchanged)cout<<u[it]<<" "<<v[it]<<endl;
        sort(unchanged.begin(),unchanged.end(),[&](int const a,int const b)
        {return d[a]>d[b];});
        sort(ask.begin(),ask.end(),[&](int const a,int const b)
        {return w[a]>w[b];});
        int ptr=0;
        for(auto it:ask)
        {
            while(ptr<unchanged.size()&&d[unchanged[ptr]]>=w[it]){combine(u[unchanged[ptr]],v[unchanged[ptr]]);ptr++;}
            int prev_sz=stk.size();
            for(auto it2:tojoin[it-l])stk.push(combine(u[it2],v[it2]));
            ans[it]=sz[find_p(s[it])];
            //cout<<it<<" "<<ptr<<" "<<s[it]<<" "<<w[it]<<" "<<ans[it]<<endl;
            roll_back(prev_sz);
        }
    }
    for(int i=1;i<=q;i++)if(t[i]==2)cout<<ans[i]<<endl;
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void roll_back(int)':
bridges.cpp:37:21: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |     while(stk.size()>a)
      |           ~~~~~~~~~~^~
bridges.cpp: In function 'int main()':
bridges.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |             while(ptr<unchanged.size()&&d[unchanged[ptr]]>=w[it]){combine(u[unchanged[ptr]],v[unchanged[ptr]]);ptr++;}
      |                   ~~~^~~~~~~~~~~~~~~~~

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