Submission #1071912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071912		alexdd	Bridges (APIO19_bridges)	C++17	100 / 100	1750 ms	7900 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
const int BUC = 1100;
pair<int,int> edges[100005];
int w[100005],curw[100005];
int tip[100005],b[100005],c[100005];
int rez[100005];
bool isbanned[100005];
bool cmp_edge(int x, int y)
{
    return w[x]>w[y];
}
bool cmp_qry(int x, int y)
{
    return c[x]>c[y];
}
struct DSU_str
{
    int siz[100005],father[100005];
    vector<pair<int,pair<int,int>>> history;
    DSU_str(int N)
    {
        for(int i=1;i<=N;i++)
            siz[i]=1,father[i]=i;
    }
    int gas(int x)
    {
        if(father[x]==x)
            return x;
        return gas(father[x]);
    }
    void unite(int x, int y)
    {
        x = gas(x);
        y = gas(y);
        if(x==y)
            return;
        if(siz[x]<siz[y])
            swap(x,y);
        history.push_back({1,{x,siz[x]}});
        siz[x]+=siz[y];
        history.push_back({2,{y,father[y]}});
        father[y]=x;
    }
    void rollback(int t)
    {
        while((int)history.size() > t)
        {
            if(history.back().first==1) siz[history.back().second.first] = history.back().second.second;
            else father[history.back().second.first] = history.back().second.second;
            history.pop_back();
        }
    }
    int getsiz(int x)
    {
        return siz[gas(x)];
    }
};

signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m,q;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>edges[i].first>>edges[i].second>>w[i];
    }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>tip[i]>>b[i]>>c[i];
    }
    for(int le=1;le<=q;le+=BUC)
    {
        int ri=min(q,le+BUC-1);
        vector<int> qrys;
        for(int i=1;i<=m;i++) isbanned[i]=0;
        for(int i=le;i<=ri;i++)
        {
            if(tip[i]==1) isbanned[b[i]]=1;
            else qrys.push_back(i);
        }
        vector<int> ids_good,ids_ban;
        for(int i=1;i<=m;i++)
        {
            if(isbanned[i])
            {
                ids_ban.push_back(i);
            }
            else
            {
                ids_good.push_back(i);
            }
        }
        sort(ids_good.begin(),ids_good.end(),cmp_edge);
        sort(qrys.begin(),qrys.end(),cmp_qry);
        int poz=-1;
        DSU_str dsu(n);
        for(auto x:qrys)
        {
            while(poz+1 < ids_good.size() && w[ids_good[poz+1]] >= c[x])
            {
                poz++;
                dsu.unite(edges[ids_good[poz]].first, edges[ids_good[poz]].second);
            }
            int copt = dsu.history.size();
            for(auto y:ids_ban)
                curw[y]=w[y];
            for(int i=le;i<x;i++)
                if(tip[i]==1)
                    curw[b[i]]=c[i];
            for(auto y:ids_ban)
                if(curw[y] >= c[x])
                    dsu.unite(edges[y].first, edges[y].second);
            rez[x] = dsu.getsiz(b[x]);
            dsu.rollback(copt);
        }
        for(int i=le;i<=ri;i++)
            if(tip[i]==1)
                w[b[i]]=c[i];
    }
    for(int i=1;i<=q;i++)
        if(tip[i]==2)
            cout<<rez[i]<<"\n";
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:102:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |             while(poz+1 < ids_good.size() && w[ids_good[poz+1]] >= c[x])
      |                   ~~~~~~^~~~~~~~~~~~~~~~~

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