Submission #743916

#	Time	Username	Problem	Language	Result	Execution time	Memory
743916		PixelCat	Bridges (APIO19_bridges)	C++14	100 / 100	2886 ms	16012 KiB

bridges

/*     code by PixelCat     */
/*         meow owo         */

#include <bits/stdc++.h>
#define int LL  //__int128
#define double long double
using namespace std;
using LL = long long;
// using i128 = __int128_t;
using ull = unsigned long long;
using pii = pair<int, int>;

#define For(i, a, b) for (int i = a; i <= b; i++)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define F first
#define S second

#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (int)(998244353)
// #define MOD (int)((LL)1'000'000'007)
#define INF (int)(4e18)
#define EPS (1e-6)

namespace PixelCat {

#ifdef NYAOWO
#include "/home/pixelcat/yodayo/meow/library/debug.hpp"
inline void USACO(const string &s) {
    cerr << "USACO: " << s << "\n";
}

#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

#endif

inline void NYA() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
inline int gcd(int a, int b) {
    return __gcd(a, b);
}
inline int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}
int fpow(int b, int p, const int &mod = MOD) {
    int ans = 1;
    for (; p; p >>= 1, b = b * b % mod)
        if (p & 1) ans = ans * b % mod;
    return ans;
}
template <typename T>
inline void chmin(T &_a, const T &_b) {
    if (_b < _a) _a = _b;
}
template <typename T>
inline void chmax(T &_a, const T &_b) {
    if (_b > _a) _a = _b;
}
mt19937_64 rng(
    chrono::steady_clock::now().time_since_epoch().count());

} // namespace PixelCat
using namespace PixelCat;

const int MAXN = 50010;
const int MAXM = 100010;
const int MAXQ = 100010;
const int BLK = 500;

struct DSU {
    int p[MAXN];
    int siz[MAXN];
    vector<pii> op;
    void init() {
        memset(p, 0, sizeof(p));
        fill(siz, siz + MAXN, 1);
        op.clear();
    }
    int find(int n) {
        if(!p[n]) return n;
        return find(p[n]);
    }
    void uni(int a, int b, bool rec = false) {
        a = find(a); b = find(b);
        if(siz[a] < siz[b]) swap(a, b);
        if(rec) op.eb(a, b);
        if(a == b) return;
        p[b] = a;
        siz[a] += siz[b];
    }
    void undo() {
        int a, b;
        tie(a, b) = op.back();
        op.pop_back();
        if(a == b) return;
        siz[a] -= siz[b];
        p[b] = 0;
    }
    void undo_all() {
        while(sz(op)) undo();
    }
    int size(int n) {
        return siz[find(n)];
    }
} dsu;

struct Query {
    int op, x, y;
    // op: 0 for update, 1~q for queries
} qry[MAXQ];
int ans[MAXQ];

pii ed[MAXM];
int w[MAXM];

void solve(int m, int l, int r) {
    // identify bad edges
    // sort good edges
    // sort queries
    vector<pair<pii, int>> e;
    For(i, 1, m) e.eb(ed[i], w[i]);
    vector<int> bad;
    vector<pii> vq;  // {index, weight}
    For(i, l, r) {
        if(!qry[i].op) {
            int eid = qry[i].x;
            e[eid - 1].S = -1;
            bad.eb(eid);
        } else {
            vq.eb(i, qry[i].y);
        }
    }
    sort(all(bad)); bad.erase(unique(all(bad)), bad.end());
    sort(all(e), [&](pair<pii, int> &a, pair<pii, int> &b) {
        return a.S < b.S;
    });
    sort(all(vq), [&](pii &a, pii &b) {
        return a.S < b.S;
    });

    dsu.init();

    // do queries while adding edges
    while(!vq.empty()) {
        int qid = vq.back().F;
        Query &q = qry[qid];
        vq.pop_back();

        // add good edges
        while(sz(e) && e.back().S >= q.y) {
            pii p = e.back().F;
            e.pop_back();
            dsu.uni(p.F, p.S);
        }

        // update bad edges & add to dsu
        For(i, l, qid) if(!qry[i].op) {
            swap(w[qry[i].x], qry[i].y);
        }
        for(int &eid:bad) if(w[eid] >= q.y) {
            dsu.uni(ed[eid].F, ed[eid].S, true);
        }

        // make query
        ans[qid] = dsu.size(q.x);

        // recover bad edges & undo dsu
        dsu.undo_all();
        Forr(i, qid, l) if(!qry[i].op) {
            swap(w[qry[i].x], qry[i].y);
        }
    }

    // actually make updates
    For(i, l, r) if(!qry[i].op) {
        Query &q = qry[i];
        w[q.x] = q.y;
    }
}

int32_t main() {
    NYA();
    // nyaacho >/////<
    int n, m; cin >> n >> m;
    For(i, 1, m) {
        cin >> ed[i].F >> ed[i].S >> w[i];
    }
    int q; cin >> q;
    For(i, 1, q) {
        auto &qr = qry[i];
        cin >> qr.op >> qr.x >> qr.y;
        qr.op--;
    }

    for(int i = 1; i <= q; i += BLK) {
        solve(m, i, min(i + BLK - 1, q));
    }
    For(i, 1, q) if(ans[i]) 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