Submission #146059

#	Time	Username	Problem	Language	Result	Execution time	Memory
146059		Bodo171	Bridges (APIO19_bridges)	C++14	30 / 100	3095 ms	26600 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,norm;
vector<int> ad[nmax];
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],viz[nmax];
int ops,n,m,q,i,nr,j,sum;
int finds(int x)
{
    int y=x,aux;
    while(x!=tt[x])
        x=tt[x];
    while(y!=x)
    {
        aux=tt[y];
        tt[y]=x;
        y=aux;
    }
    return x;
}
void unite(int A,int B)
{
    if(A==B) return;
    if(rg[A]<rg[B]) swap(A,B);
    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--;
    }
}
void add(int x,int y)
{
    ad[x].push_back(y);
    ad[y].push_back(x);
}
void res(int x)
{
    ad[x].resize(0);
    viz[x]=0;
}
void dfs(int x)
{
    viz[x]=1;sum+=rg[x];
    for(int it=0;it<ad[x].size();it++)
        if(!viz[ad[x][it]])
           dfs(ad[x][it]);
}
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;
                    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)
                            add(finds(a[spec[j]]),finds(b[spec[j]]));
                    sum=0;
                    dfs(finds(wh[ind]));
                    ans[ind]=sum;
                    res(finds(wh[ind]));
                     for(j=0; j<spec.size(); j++)
                        {
                            res(finds(a[spec[j]]));
                            res(finds(b[spec[j]]));
                            w[spec[j]]=ini[spec[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 'void dfs(int)':
bridges.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int it=0;it<ad[x].size();it++)
                  ~~^~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:83:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<norm.size();i++)
             ~^~~~~~~~~~~~
bridges.cpp:127:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for(j=0; j<spec.size(); j++)
                              ~^~~~~~~~~~~~
bridges.cpp:134:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                      for(j=0; j<spec.size(); j++)
                               ~^~~~~~~~~~~~
bridges.cpp:148: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