Submission #993407

#	Time	Username	Problem	Language	Result	Execution time	Memory
993407		Chris_Black	Bridges (APIO19_bridges)	C++17	100 / 100	1942 ms	15160 KiB

bridges

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORR(i, a, b) for(int i = a; i >= b; --i)
#define pii pair<int, int>
#define ff first
#define ss second
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define ll long long

using namespace std;
const int N = 50009, M = 1e5 + 9, BUCKET = 333;

int n, m, q, ans[M];
bool seen[M], mod[M];

struct edge
{
    int u, v, d, id;

    bool operator < (edge const& oth) const noexcept
    {
        return d == oth.d ? id < oth.id : d < oth.d;
    }

    bool operator > (edge const& oth) const noexcept
    {
        return d == oth.d ? id > oth.id : d > oth.d;
    }
};
vector<edge> edges;

struct query
{
    int t, p, v, ans;
};
vector<query> qs;

int dsu[N], sz[N];
stack<pii> stk;
int find(int x){return dsu[x] ? find(dsu[x]) : x;}
void unite(int x, int y)
{
    x = find(x), y = find(y);

    if(x == y)return;

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

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

    stk.push({x, y});
}
void RollBack()
{
    if(stk.empty())return;

    int x = stk.top().ff, y = stk.top().ss;
    stk.pop();

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

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

    cin >> n >> m;

    FOR(i, 1, n)sz[i] = 1;

    edges.resize(m);
    FOR(i, 0, m - 1)
    {
        cin >> edges[i].u >> edges[i].v >> edges[i].d;
        edges[i].id = i + 1;
    }

    cin >> q;
    qs.resize(q);
    FOR(i, 0, q - 1)
        cin >> qs[i].t >> qs[i].p >> qs[i].v;

    set<edge, greater<>> ing;
    for(auto e : edges)ing.insert(e);

    for(int k = 0; k < q; k += BUCKET)
    {
        while(!stk.empty())stk.pop();
        FOR(i, 0, n + 1)
        {
            dsu[i] = 0;
            sz[i] = 1;
        }

        vector<int> st;
        priority_queue<pii> toans;
        for(int i = k; i < min(q, k + BUCKET); ++i)
            if(qs[i].t == 1)
            {
                mod[qs[i].p] = true;

                auto ind = ing.find(edges[qs[i].p - 1]);
                if(ind != ing.end())ing.erase(ind);

                st.pb(qs[i].p);
            }
            else toans.push({qs[i].v, i});

        auto it = ing.begin();

        while(!toans.empty())
        {
            int dx = toans.top().ff, p = toans.top().ss;
            toans.pop();

            while(it != ing.end() && it -> d >= dx)
            {
                unite(it -> u, it -> v);
                ++ it;
            }
            int s = stk.size();

            for(int i = p; i >= k; --i)
                if(qs[i].t == 1 && !seen[qs[i].p])
                {
                    seen[qs[i].p] = true;
                    if(qs[i].v >= dx)unite(edges[qs[i].p - 1].u, edges[qs[i].p - 1].v);
                }

            for(auto ind : st)
                if(!seen[ind] && edges[ind - 1].d >= dx)
                    unite(edges[ind - 1].u, edges[ind - 1].v);

            ans[p] = sz[find(qs[p].p)];

            for(int i = p; i >= k; --i)
                if(qs[i].t == 1)
                    seen[qs[i].p] = false;

            while((int)stk.size() != s)RollBack();
        }

        for(int i = min(q, k + BUCKET) - 1; i >= k; --i)
            if(qs[i].t == 1 && mod[qs[i].p])
            {
                mod[qs[i].p] = false;
                edges[qs[i].p - 1].d = qs[i].v;
                ing.insert(edges[qs[i].p - 1]);
            }
    }

    FOR(i, 0, q - 1)
        if(qs[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