Submission #1345929

#TimeUsernameProblemLanguageResultExecution timeMemory
1345929SemicolonBridges (APIO19_bridges)C++20
100 / 100
2944 ms59332 KiB
/**
 *     Author: Lưu Diệp Thành (Save Diệp Thành)
 *     Le Hong Phong High School for the Gifted (i2528)
**/
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ll long long
#define ushort unsigned short
#define FOR(i,l,r) for(int i = (l), _r = (r); i <= _r; i++)
#define FORN(i,r,l) for(int i = (r), _l = (l); i >= _l; i--)
#define endl '\n'
#define sz(x) (int)x.size()
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)
#define ins insert
#define segleft (id<<1)
#define segright (id<<1|1)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
const int MOD = 1e9+7;

struct DisjointSet {
    vector<int> par, num;
    vector<pair<int,int>> history;
    int n;

    DisjointSet() {}

    void init(int _n) {
        n = _n;
        par.assign(n+5, 0);
        num.assign(n+5, 0);
        iota(all(par), 0);
        fill(all(num), 1);
        vector<pair<int,int>>().swap(history);
    }

    int findpar(int u) {
        return (par[u] == u ? u : findpar(par[u]));
    }

    int getTime() {
        return sz(history);
    }

    bool unite(int u, int v) {
        u = findpar(u);
        v = findpar(v);
        if (u==v) return false;

        history.pb({u, num[u]});
        history.pb({v, num[v]});

        if (num[u] < num[v]) swap(u,v);
        par[v] = u;
        num[u] += num[v];
        return true;
    }

    void rollback(int time) {
        while(sz(history) > time) {
            pair<int,int> cur = history.back();
            history.pop_back();
            int oldu = cur.fi, oldnum = cur.se;
            par[oldu] = oldu;
            num[oldu] = oldnum;
        }
    }
};

const int N = 1e5+5;
int u[N], v[N], w[N];
int t[N], x[N], y[N];
int n,m,q;
int ans[N];
vector<int> JoinSet[N];
bool change[N];

void Semicolon() {
    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 B = sqrt(q);
    DisjointSet dsu;
    dsu.init(n);

    for(int left = 1; left <= q; left += B) {
        int right = min(q, left + B - 1);
        fill(change+1, change+m+1, false);

        vector<int> ask, update, unchange;

        FOR(i, left, right) {
            if (t[i] == 1) {
                update.pb(i);
                change[x[i]] = true;
            } else {
                ask.pb(i);
            }
        }

        FOR(i, 1, m) if (!change[i]) unchange.pb(i);

        FOR(i, left, right) {
            if (t[i] == 1) {
                w[x[i]] = y[i];
            } else {
                vector<int>().swap(JoinSet[i]);
                for(int j : update) {
                    if (w[x[j]] >= y[i]) JoinSet[i].pb(x[j]);
                }
            }
        }

        sort(all(ask), [](int a, int b) {
            return y[a] > y[b];
        });
        sort(all(unchange), [](int a, int b) {
            return w[a] > w[b];
        });

        dsu.init(n);
        int j = 0;
        for(int i : ask) {
            while(j < sz(unchange) && w[unchange[j]] >= y[i]) {
                int idx = unchange[j];
                dsu.unite(u[idx], v[idx]);
                j++;
            }

            int timer = dsu.getTime();
            for(int j : JoinSet[i]) {
                dsu.unite(u[j], v[j]);
            }
            ans[i] = dsu.num[dsu.findpar(x[i])];
            dsu.rollback(timer);
        }
    }

    FOR(i, 1, q) {
        if (t[i] == 2) {
            cout << ans[i] << endl;
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    if (fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
    int t = 1;
    //cin >> t;
    while(t--) Semicolon();

    cerr << endl;
    cerr << "Time elapsed: " << TIME << " s.\n ";
    return (0 ^ 0);
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:157:41: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |     if (fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
      |                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...