Submission #956848

#	Time	Username	Problem	Language	Result	Execution time	Memory
956848		underwaterkillerwhale	Bridges (APIO19_bridges)	C++17	100 / 100	2470 ms	12024 KiB

bridges

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 1e5 + 7;
const int Mod = 1e9 + 7;
const int szBL = 500;
const int INF = 2e9 + 7;
const int BASE = 137;

struct Edge {
    int u, v, id, w;
    Edge (int u = 0, int v = 0, int id = 0, int w = 0) : u(u), v(v), id(id), w(w) {};
};
struct Edge2 {
    int u, v, w;

};
struct Query {
    int typ, u, v;
};

struct Data {
    int id, u, v;
};

struct Disjoin_Set_Union {
    struct State {
        int labu, labv, szu, szv;
        State (int labu = 0, int labv= 0, int szu = 0, int szv= 0) : labu(labu), labv(labv), szu(szu), szv(szv) {};
    };
    int lab[N], sz[N];
    stack<State> op;

    void init (int n) {
        rep (i, 1, n) lab[i] = i, sz[i] = 1;
        stack<State> ().swap(op);
    }

    int Find (int u) {
        if (u == lab[u]) return u;
        return Find(lab[u]);
    }

    bool Join (int u, int v) {
        u = Find(u);
        v = Find(v);
        if (u == v) return 0;
        op.push(State(u, v, sz[u], sz[v]));
        if (sz[u] < sz[v]) swap(u, v);
        lab[v] = u;
        sz[u] += sz[v];
        return 1;
    }

    void roll_back() {
        assert(!op.empty());
        State cur = op.top();
        lab[cur.labu] = cur.labu;
        lab[cur.labv] = cur.labv;
        sz[cur.labu] = cur.szu;
        sz[cur.labv] = cur.szv;
        op.pop();
    }

    int get (int u) {
        return sz[Find(u)];
    }
}DSU;



int n, m, Q;
int a[N];
Edge2 ini_edge[N];
Query qr[N];

bool changed[N];
bool dd[N];

void solution () {
    cin >> n >> m;
    rep (i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        ini_edge[i] = {u, v, w};
    }
    cin >> Q;
    rep (i, 1, Q) {
        cin >> qr[i].typ >> qr[i].u >> qr[i].v;
    }
    vector<int> Answer(Q + 1, 0);
    for (int qi = 1; qi <= Q; qi += szBL) {
        static vector<Data> Ans; vector<Data> ().swap(Ans);
        static vector<Data> Ask; vector<Data> ().swap(Ask);
        static vector<Edge> edges; vector<Edge> ().swap(edges);
        DSU.init(n);
        rep (i, 1, m) changed[i] = 0, edges.pb({ini_edge[i].u, ini_edge[i].v, i, ini_edge[i].w});
        int L = qi, R = min(Q, qi + szBL - 1);
        rep (i, L, R) {
            if (qr[i].typ == 1) {
                Ask.push_back({i, qr[i].u, qr[i].v});
                changed[qr[i].u] = 1;
            }
            else Ans.push_back({i, qr[i].u, qr[i].v});
        }
        sort (ALL(edges), [] (Edge A, Edge B) { return A.w > B.w; });
        sort (ALL(Ans),   [] (Data A, Data B) { return A.v > B.v || (A.v == B.v && A.id < B.id); });
        int Eptr = 0;
        rep (i, 0, SZ(Ans) - 1) {
            int cur_values = Ans[i].v;
            while (Eptr < m && edges[Eptr].w >= cur_values) {
                if (changed[edges[Eptr].id] == 0) {
                    DSU.Join(edges[Eptr].u, edges[Eptr].v);
//                    cout << edges[Eptr].u <<" "<<edges[Eptr].v <<" hi\n";
                }
                ++Eptr;
            }
            static vector<Data> vec;
            vec = {Ans[i]};
            while (i < SZ(Ans) - 1 && Ans[i].v == Ans[i + 1].v) vec.push_back(Ans[i + 1]), ++i;
            int rightmost = -1;
            rep (j, 0, SZ(vec) - 1) {
//                cout << vec[j].id <<"jijoi\n";
                while (rightmost < SZ(Ask) - 1 && Ask[rightmost + 1].id < vec[j].id) ++rightmost;
                int num_roll = 0;
                reb (k, rightmost, 0) {
                    if (dd[Ask[k].u]) continue;
                    if (Ask[k].v >= vec[j].v) {
                        num_roll += DSU.Join(ini_edge[Ask[k].u].u, ini_edge[Ask[k].u].v);
                    }
                    dd[Ask[k].u] = 1;
                }
                rep (k, rightmost + 1, SZ(Ask) - 1)  {
                    if (!dd[Ask[k].u] && ini_edge[Ask[k].u].w >= vec[j].v) {
                        num_roll += DSU.Join (ini_edge[Ask[k].u].u, ini_edge[Ask[k].u].v);
//                        cout << vec[j].id<<" JOIN: "<<ini_edge[Ask[k].u].u<<" "<<ini_edge[Ask[k].u].v <<"\n";
                    }
                }
                Answer[vec[j].id] = DSU.get(vec[j].u);
                while (num_roll--) DSU.roll_back();
                rep (k, 0, rightmost) dd[Ask[k].u] = 0;
            }
        }
        ///update lastest_values to Edge.w
        rep (i, L, R) if (qr[i].typ == 1) ini_edge[qr[i].u].w = qr[i].v;
    }
    rep (i, 1, Q) if (qr[i].typ == 2) cout << Answer[i] <<"\n";
}

#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);

int main() {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
3 4
1 2 5
2 3 2
3 1 4
2 3 8
5
2 1 5
1 4 1
2 2 5
1 1 1
2 3 2
*/

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