Submission #887083

#	Time	Username	Problem	Language	Result	Execution time	Memory
887083		andrei_boaca	Bridges (APIO19_bridges)	C++17	100 / 100	1637 ms	10524 KiB

bridges

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
const int bucksize=1000;
int n,m,q;
pii g[100005];
int cost[100005],aux[100005],par[100005],sz[100005],sol[100005];
bool changed[100005];
struct date
{
    int tip,a,b;
};
vector<date> buff;
int getpar(int nod)
{
    while(par[nod]!=nod)
        nod=par[nod];
    return nod;
}
bool comp(date a, date b)
{
    if(a.b!=b.b)
        return a.b>b.b;
    return a.tip<b.tip;
}
void solve()
{
    for(int i=1;i<=m;i++)
    {
        changed[i]=0;
        aux[i]=cost[i];
    }
    vector<int> modif;
    vector<date> ev;
    for(int i=0;i<buff.size();i++)
    {
        sol[i]=0;
        int tip=buff[i].tip;
        if(tip==1)
        {
            modif.push_back(buff[i].a);
            changed[buff[i].a]=1;
        }
        else
            ev.push_back({2,i,buff[i].b});
    }
    for(int i=1;i<=m;i++)
        if(!changed[i])
            ev.push_back({1,i,cost[i]});
    sort(ev.begin(),ev.end(),comp);
    for(int i=1;i<=n;i++)
    {
        sz[i]=1;
        par[i]=i;
    }
    for(date z:ev)
    {
        int tip=z.tip;
        if(tip==1)
        {
            int ind=z.a;
            int a=getpar(g[ind].first);
            int b=getpar(g[ind].second);
            if(a!=b)
            {
                if(sz[a]<sz[b])
                    swap(a,b);
                par[b]=a;
                sz[a]+=sz[b];
            }
        }
        else
        {
            int p=z.a;
            for(int i:modif)
                cost[i]=aux[i];
            for(int i=0;i<=p;i++)
                if(buff[i].tip==1)
                {
                    int ind=buff[i].a;
                    int c=buff[i].b;
                    cost[ind]=c;
                }
            int nod=buff[p].a;
            int c=buff[p].b;
            stack<pii> stiva;
            for(int i:modif)
                if(cost[i]>=c)
                {
                    int a=getpar(g[i].first);
                    int b=getpar(g[i].second);
                    if(a!=b)
                    {
                        if(sz[a]<sz[b])
                            swap(a,b);
                        par[b]=a;
                        sz[a]+=sz[b];
                        stiva.push({a,b});
                    }
                }
            sol[p]=sz[getpar(nod)];
            while(!stiva.empty())
            {
                int a=stiva.top().first;
                int b=stiva.top().second;
                stiva.pop();
                sz[a]-=sz[b];
                par[b]=b;
            }
        }
    }
    for(int i=0;i<buff.size();i++)
        if(sol[i]!=0)
            cout<<sol[i]<<'\n';
    for(int i=1;i<=m;i++)
        cost[i]=aux[i];
    for(date z:buff)
        if(z.tip==1)
            cost[z.a]=z.b;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[i]={a,b};
        cost[i]=c;
    }
    cin>>q;
    while(q--)
    {
        int tip,a,b;
        cin>>tip>>a>>b;
        buff.push_back({tip,a,b});
        if(buff.size()==bucksize)
        {
            solve();
            buff.clear();
        }
    }
    if(!buff.empty())
        solve();
    buff.clear();
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void solve()':
bridges.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<date>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0;i<buff.size();i++)
      |                 ~^~~~~~~~~~~~
bridges.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<date>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for(int i=0;i<buff.size();i++)
      |                 ~^~~~~~~~~~~~

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