Submission #199236

#	Time	Username	Problem	Language	Result	Execution time	Memory
199236		Alexa2001	Bridges (APIO19_bridges)	C++17	100 / 100	2994 ms	24268 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e5 + 5, B = 1044;

struct Edge
{
    int x, y, c;
};

struct Query
{
    int t, x, c;
};

int n, m, nq, lim;
int last[Nmax], nxt[Nmax], prv[Nmax];
Edge edge[Nmax];
Query q[Nmax];
int ans[Nmax];

vector<int> modif, query[Nmax], when[Nmax];


static void read()
{
    int i;
    cin >> n >> m;

    for(i=1; i<=m; ++i)
        cin >> edge[i].x >> edge[i].y >> edge[i].c;

    cin >> nq;
    for(i=1; i<=nq; ++i) cin >> q[i].t >> q[i].x >> q[i].c;

    for(i=1; i<=nq; ++i)
        if(q[i].t == 1)
        {
            prv[i] = last[q[i].x];
            last[q[i].x] = i;
        }

    for(i=1; i<=m; ++i) last[i] = 1e9;

    for(i=nq; i; --i)
        if(q[i].t == 1)
        {
            nxt[i] = last[q[i].x];
            last[q[i].x] = i;
        }

    for(i=1; i<=m; ++i) last[i] = 0;
}

static void normalize()
{
    vector<int> all;
    int i;

    for(i=1; i<=m; ++i) all.push_back(edge[i].c);

    for(i=1; i<=nq; ++i)
        if(q[i].t == 1)
            all.push_back(q[i].c);

    sort(all.begin(), all.end());
    all.erase( unique(all.begin(), all.end()), all.end() );

    lim = all.size();

    for(i=1; i<=m; ++i)
        edge[i].c = lower_bound(all.begin(), all.end(), edge[i].c) - all.begin();

    for(i=1; i<=nq; ++i)
        q[i].c = lower_bound(all.begin(), all.end(), q[i].c) - all.begin();
}



struct DisjDataSet
{
    int t[Nmax];
    int s[Nmax];
    int tip;

    vector<int> who, old_size;

    int boss(int x)
    {
        if(x == t[x]) return x;
        int dad = boss(t[x]);
        if(tip == 1) t[x] = dad;
        return dad;
    }

    void reset()
    {
        int i; tip = -1;
        for(i=1; i<=n; ++i) t[i] = i, s[i] = 1;
    }

    void unite(int x, int y)
    {
        x = boss(x); y = boss(y);
        if(x == y) return;

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

        if(tip == 2)
            who.push_back(x), old_size.push_back(s[x]);

        t[x] = y;
        s[y] += s[x];
    }

    void undo()
    {
        int i;
        for(i=who.size()-1; i>=0; --i)
            s[t[who[i]]] -= old_size[i], t[who[i]] = who[i];

        who.clear(); old_size.clear();
    }

    int get_size(int x)
    {
        x = boss(x);
        return s[x];
    }

} forest;



static void solve(int start)
{
    int i;

    ///
    modif.clear();
    for(i=0; i<=lim; ++i)
        when[i].clear(), query[i].clear();

    forest.reset();
    ///

    for(i=start; i<start+B && i<=nq; ++i)
        if(q[i].t == 1)
        {
            last[q[i].x] = i;
            modif.push_back(i);
        }
        else query[q[i].c].push_back(i);

    for(i=1; i<=m; ++i)
        if(last[i] < start)
            when[edge[i].c].push_back(i);

    for(i=lim; i>=0; --i)
    {
        ///
        forest.tip = 1;

        for(auto &it : when[i])
            forest.unite(edge[it].x, edge[it].y);
        ///

        forest.tip = 2;
        for(auto &it : query[i])
        {
            for(auto &j : modif)
                if( (j < it && nxt[j] > it && q[j].c >= i) || (prv[j] < start && j > it && edge[q[j].x].c >= i) )
                    forest.unite(edge[q[j].x].x, edge[q[j].x].y);

            ans[it] = forest.get_size(q[it].x);
            forest.undo();
        }
    }

    for(auto &j : modif)
        edge[q[j].x].c = q[j].c;
}

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);


    read();
    normalize();

    int i;
    for(i=1; i<=nq; i+=B)
        solve(i);

    for(i=1; i<=nq; ++i)
        if(q[i].t == 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