Submission #145971

#	Time	Username	Problem	Language	Result	Execution time	Memory
145971		Bodo171	Bridges (APIO19_bridges)	C++14	59 / 100	3081 ms	28032 KiB

bridges

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
const int nmax=100005;
const int buck=600;
struct event
{
    int tip,id;
}ev;
vector<event> evs[2*nmax];
vector<int> spec;
vector<int> norm;
map<int,int> act;
int tt[nmax],rg[nmax],mic[nmax],mare[nmax],a[nmax],b[nmax],w[nmax],tip[nmax],wh[nmax],cost[nmax],ap[nmax],ans[nmax],ini[nmax];
int ops,n,m,q,i,nr,j;
int finds(int x)
{
    while(x!=tt[x])
        x=tt[x];
    return x;
}
void unite(int A,int B)
{
    if(A==B) return;
    if(rg[A]<rg[B]) swap(A,B);
    ++ops;
    mic[ops]=B;mare[ops]=A;
    tt[B]=A;rg[A]+=rg[B];
}
void rollback(int lim)
{
    while(ops>lim)
    {
        tt[mic[ops]]=mic[ops];
        rg[mare[ops]]-=rg[mic[ops]];
        ops--;
    }
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i]>>w[i];
        norm.push_back(w[i]);
    }
    cin>>q;
    for(i=1;i<=q;i++)
    {
        cin>>tip[i]>>wh[i]>>cost[i];
        norm.push_back(cost[i]);
    }
    sort(norm.begin(),norm.end());
    norm.erase(unique(norm.begin(),norm.end()),norm.end());
    int lim=norm.size();
    for(i=0;i<norm.size();i++)
      act[norm[i]]=i+1;
    for(i=1;i<=m;i++)
        w[i]=act[w[i]];
    for(i=1;i<=q;i++)
        cost[i]=act[cost[i]];
    for(int bg=1;bg<=q;bg+=buck)
    {
        nr=0;
        ops=0;
        spec.clear();
        for(i=1;i<=n;i++)
            tt[i]=i,rg[i]=1;
        for(i=bg;i<min(bg+buck,q+1);i++)
        {
            if(tip[i]==1)
            {
                spec.push_back(wh[i]);
                ap[wh[i]]=1;
                ini[wh[i]]=w[wh[i]];
            }
            else
            {
                evs[cost[i]].push_back({1,i});
            }
        }
        for(i=1;i<=m;i++)
            if(!ap[i])
              evs[w[i]].push_back({0,i});
        int sz;
        for(i=lim;i>=1;i--)
        {
            sz=evs[i].size();
            for(int it=sz-1;it>=0;it--)
            {
                ev=evs[i][it];
                if(ev.tip==0)
                    unite(finds(a[ev.id]),finds(b[ev.id]));
                else
                {
                    int ind=ev.id,de_unde=ops;
                    for(j=bg; j<ind; j++)
                        if(tip[j]==1)
                        {
                            w[wh[j]]=cost[j];
                        }
                    for(j=0; j<spec.size(); j++)
                        if(w[spec[j]]>=i)
                        {
                            unite(finds(a[spec[j]]),finds(b[spec[j]]));
                        }
                    ans[ind]=rg[finds(wh[ind])];
                    rollback(de_unde);
                    for(j=bg; j<ind; j++)
                        if(tip[j]==1)
                        {
                            w[wh[j]]=ini[wh[j]];
                        }
                }
            }
        }
        for(i=1;i<=lim;i++)
            evs[i].resize(0);
        for(i=bg;i<min(bg+buck,q+1);i++)
           if(tip[i]==1)
              w[wh[i]]=cost[i];
        for(i=0;i<spec.size();i++)
            ap[spec[i]]=0;
    }
    for(i=1;i<=q;i++)
        if(tip[i]==2)
        cout<<ans[i]<<'\n';
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:61:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<norm.size();i++)
             ~^~~~~~~~~~~~
bridges.cpp:107:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for(j=0; j<spec.size(); j++)
                              ~^~~~~~~~~~~~
bridges.cpp:127:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<spec.size();i++)
                 ~^~~~~~~~~~~~

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