Submission #522254

#	Time	Username	Problem	Language	Result	Execution time	Memory
522254		Aldas25	Bridges (APIO19_bridges)	C++14	14 / 100	1330 ms	524292 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;

const int MAXN = 500100;

int par[MAXN], sz[MAXN];
stack<int> st;

int find (int a) {return par[a] = par[a]==a ? a : find(par[a]);}

bool same (int a, int b) {return find(a) == find(b);}

void unite (int a, int b) {
    a = find(a);
    b = find(b);
    if (a==b) return;
    if (sz[b] > sz[a]) swap(a,b);

    st.push(b);
    par[b] = a;
    sz[a] += sz[b];
}

void rollback (int prevSz) {
    while ((int)st.size() > prevSz) {
        int x = st.top();
        st.pop();
        sz[par[x]] -= sz[x];
        par[x] = x;
    }
}


int n, m, q;
int u[MAXN], v[MAXN], w[MAXN];
int t[MAXN], x[MAXN], y[MAXN];
const int C = 100000;
int ans[MAXN];

void dsuReset () {
    FOR(i, 1, n) {
        par[i] = i;
        sz[i] = 1;
    }
    while (!st.empty()) {st.pop();}
}

//vi changedBr, unchangedBr;
vii unchangedBr, queries;
vi updatedBr;
bool changed[MAXN];
vi toJoinBr[C+100];

int main()
{
    FAST_IO;

    cin >> n >> m;
    FOR(i, 1, m)
        cin >> u[i] >> v[i] >> w[i];

    cin >> q;
    FOR(i, 1, q)
        cin >> t[i] >> x[i] >> y[i];

    //int C = sqrt(N);  /// ****

    for (int le = 1; le <= q; le += C) {
        int ri = min(q, le + C - 1);

        dsuReset();
        unchangedBr.clear();
        updatedBr.clear();
        queries.clear();
       // FOR(i, 0, C+5) toJoinBr[i].clear();

        FOR(i, 1, m) changed[i] = false;

       // cout << " query group le = " << le << " ri = " << ri << endl;

        FOR(i, le, ri) {
            if (t[i] == 1) {
                changed[x[i]] = true;
                //updatedBr.pb(i);
            } else {
                queries.pb({y[i], i});
            }
        }

        sort(queries.begin(), queries.end());
        reverse(queries.begin(), queries.end());

        FOR(i, 1, m) {
            if (!changed[i]) unchangedBr.pb({w[i], i});
            else updatedBr.pb(i);
        }
        sort(unchangedBr.begin(), unchangedBr.end());
        reverse(unchangedBr.begin(), unchangedBr.end());

        FOR(i, le, ri) {
            if (t[i] == 1) {
                w[x[i]] = y[i];
            }
            else {
                toJoinBr[i-le].clear();
                   // cout << " i = " << i << " searching to Join" << endl;
                for (int id : updatedBr) {
                     //   cout << "   id = " << id << " wid = " << w[id] << " yi = " << y[i] << endl;
                    if (w[id] >= y[i])
                        toJoinBr[i-le].pb(id);
                }
            }
        }

        //cout << "    unchanged br: ";
        //for (auto p : unchangedBr) cout << p.s << " ";
        //cout << endl;

        int qId = 0, bId = 0;
        while (qId < (int)queries.size()) {
            if (bId < (int)unchangedBr.size() && unchangedBr[bId].f >= queries[qId].f) {
                int id = unchangedBr[bId].s;
                unite(u[id], v[id]);
                //cout << "    unitin id=" << id << "  u=" << u[id] << " v=" << v[id] << endl;
                bId++;
            } else {
                int id = queries[qId].s;
                //cout << "    query id = " << id << endl;
                int prSz = (int)st.size();
                for (int bri : toJoinBr[id-le]) {
                    unite(u[bri], v[bri]);
                  //  cout << "                unitin id= " << bri << " u = " << u[bri] << " v = " << v[bri] << endl;
                }


                ans[id] = sz[find(x[id])];
                //cout << "      found ans = " << ans[id] << endl;

                rollback(prSz);
                qId++;
            }
        }

    }

    FOR(i, 1, q) if (t[i] == 2) cout << ans[i] << "\n";

    return 0;
}

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