Submission #145954

#	Time	Username	Problem	Language	Result	Execution time	Memory
145954		Bodo171	Bridges (APIO19_bridges)	C++14	30 / 100	3066 ms	8828 KiB

bridges

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax=100005;
const int buck=300;
struct event
{
    int tip,id,c;
}ev[nmax+2*buck];
vector<int> spec;
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;
bool operator <(event unu,event doi)
{
    if(unu.c==doi.c) return unu.tip<doi.tip;
    return (unu.c>doi.c);
}
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];
    }
    cin>>q;
    for(i=1;i<=q;i++)
    {
        cin>>tip[i]>>wh[i]>>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
            {
                ev[++nr]={1,i,cost[i]};
            }
        }
        for(i=1;i<=m;i++)
            if(!ap[i])
              ev[++nr]={0,i,w[i]};
        sort(ev+1,ev+nr+1);
        for(i=1;i<=nr;i++)
        {
            if(ev[i].tip==0)
                unite(finds(a[ev[i].id]),finds(b[ev[i].id]));
            else
            {
                int ind=ev[i].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]]>=ev[i].c)
                {
                    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=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:93:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(j=0;j<spec.size();j++)
                         ~^~~~~~~~~~~~
bridges.cpp:110:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<spec.size();i++)
                 ~^~~~~~~~~~~~

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