Submission #555920

#	Time	Username	Problem	Language	Result	Execution time	Memory
555920		status_coding	Bridges (APIO19_bridges)	C++14	100 / 100	1833 ms	14328 KiB

bridges

#include <bits/stdc++.h>
//#pragma GCC target ("avx2")

using namespace std;

struct edge
{
    int x, y, w;

    edge(int x, int y, int w)
    {
        this->x = x;
        this->y = y;
        this->w = w;
    }

    bool operator< (edge b) const
    {
        return w > b.w;
    }
};

struct askS
{
    int p, w, id;

    askS(int p, int w, int id)
    {
        this->p = p;
        this->w = w;
        this->id = id;
    }

    bool operator<(askS b) const
    {
        return w > b.w;
    }
};

int n,m,q,rad;

vector<edge> e;
bool isChanged[100005];

vector<pair<int, int>> dsuS;
int dsu[100005];
int sz[100005];

vector<askS> ask;
vector<edge> unchanged;
vector<int> changed;
vector<pair<int, int>> toMerge[1005];

int tip[100005], w[100005], id[100005], poz[100005];
int ans[100005];

int dsu_par(int x)
{
    while(dsu[x] != x)
        x = dsu[x];
    return x;
}

void dsu_merge(int x, int y)
{
    x = dsu_par(x);
    y = dsu_par(y);

    if(x == y)
        return;

    if(sz[y] > sz[x])
        swap(x, y);

    dsuS.push_back({x, y});

    dsu[y] = x;
    sz[x] += sz[y];
}

void dsu_rollback(int last)
{
    while((int)dsuS.size() > last)
    {
        int x = dsuS.back().first;
        int y = dsuS.back().second;
        dsuS.pop_back();

        sz[x] -= sz[y];
        dsu[y] = y;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>m;
    rad = 1000;

    e.push_back(edge(0, 0, 0));
    for(int i=1; i<=m; i++)
    {
        long long x, y, w;
        cin>>x>>y>>w;

        e.push_back(edge(x, y, w));
    }

    cin>>q;
    for(int i=1; i<=q; i++)
    {
        cin>>tip[i];

        if(tip[i] == 1)
            cin>>id[i]>>w[i];
        else
            cin>>poz[i]>>w[i];
    }

    for(int l=1; l<=q; l+=rad)
    {
        int r = min(l+rad-1, q);

        //cout<<"bucket: "<<l<<' '<<r<<'\n';

        changed.clear();
        unchanged.clear();
        ask.clear();

        dsuS.clear();
        for(int i=1;i<=n;i++)
        {
            dsu[i] = i;
            sz[i] = 1;
        }

        for(int i=0;i<=rad;i++)
            toMerge[i].clear();

        for(int i=1; i<=m; i++)
            isChanged[i] = false;


        for(int i=l; i<=r; i++)
        {
            if(tip[i] == 1)
            {
                if(!isChanged[ id[i] ])
                    changed.push_back(id[i]);

                isChanged[ id[i] ] = true;
            }
        }

        for(int i=l; i<=r; i++)
        {
            if(tip[i] == 1)
                e[ id[i] ].w = w[i];
            else
            {
                ask.push_back(askS( poz[i], w[i], i ));

                for(int id : changed)
                    if(e[id].w >= w[i])
                        toMerge[ i-l ].push_back({e[id].x, e[id].y});
            }
        }

        for(int i=1; i<=m; i++)
            if(!isChanged[i])
                unchanged.push_back(e[i]);

        sort(ask.begin(), ask.end());
        sort(unchanged.begin(), unchanged.end());

        int j=0;
        for(int i=0; i<(int)ask.size(); i++)
        {
            while(j < (int)unchanged.size() && unchanged[j].w >= ask[i].w)
            {
                dsu_merge(unchanged[j].x, unchanged[j].y);
                j++;
            }

            int last = dsuS.size();
            for(auto it : toMerge[ ask[i].id - l ])
                dsu_merge(it.first, it.second);

            ans[ ask[i].id ] = sz[ dsu_par(ask[i].p) ];

            dsu_rollback(last);
        }
    }

    //cout<<"\n\n";
    for(int i=1; i<=q; i++)
        if(tip[i] == 2)
            cout<<ans[i]<<'\n';

    return 0;
}

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