Submission #768474

#	Time	Username	Problem	Language	Result	Execution time	Memory
768474		pandapythoner	Bridges (APIO19_bridges)	C++14	100 / 100	1235 ms	11480 KiB

bridges

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

struct DSU {
    int n;
    vector<int> t;
    vector<int> s;
    vector<int> a, b;

    void build(int _n) {
        n = _n;
        a.clear();
        b.clear();
        a.reserve(n);
        b.reserve(n);
        t.resize(n);
        s.resize(n);
        for (int i = 0; i < n; i += 1) {
            t[i] = i;
            s[i] = 1;
        }
    }

    int get(int v) {
        if (v == t[v]) {
            return v;
        }
        return get(t[v]);
    }

    void merge(int u, int v, bool save) {
        u = get(u);
        v = get(v);
        if (u == v) {
            return;
        }
        if (s[u] > s[v]) {
            swap(u, v);
        }
        t[u] = v;
        s[v] += s[u];
        if (save) {
            a.push_back(u);
            b.push_back(v);
        }
    }

    void back() {
        for (int i = (int)a.size() - 1; i >= 0; i -= 1) {
            int u = a[i];
            int v = b[i];
            t[u] = u;
            s[v] -= s[u];
        }
        a.clear();
        b.clear();
    }

    int get_size(int v) {
        return s[get(v)];
    }
};

const int b = 500;

bool comp(const pair<ll, int> &a, const pair<ll, int> &b) {
    return a > b;
}

int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> e(m);
    vector<int> d(m);
    for (int i = 0; i < m; i += 1) {
        cin >> e[i].first >> e[i].second >> d[i];
        --e[i].first;
        --e[i].second;
    }
    int qs;
    cin >> qs;
    vector<array<int, 3>> q(qs);
    for (int i = 0; i < qs; i += 1) {
        cin >> q[i][0] >> q[i][1] >> q[i][2];
        --q[i][1];
    }
    vector<int> rs(qs);
    vector<pair<ll, int>> all_sorted(m);
    for (int i = 0; i < m; i += 1) {
        all_sorted[i] = make_pair(d[i], i);
    }
    sort(rall(all_sorted));
    for (int l = 0; l < qs; l += b) {
        int r = min(qs, l + b);
        vector<int> chngd(m, 0);
        for (int i = l; i < r; i += 1) {
            if (q[i][0] == 1) {
                chngd[q[i][1]] = true;
            }
        }
        vector<pair<ll, int>> cnst_edgs;
        vector<int> nd(m);
        cnst_edgs.reserve(m);
        vector<int> nt_cnst;
        nt_cnst.reserve(b);
        for (auto [_, i] : all_sorted) {
            if (!chngd[i]) {
                cnst_edgs.push_back(make_pair(d[i], i));
            } else {
                nt_cnst.push_back(i);
            }
        }
        vector<pair<ll, int>> asks;
        asks.reserve(b);
        for (int i = l; i < r; i += 1) {
            if (q[i][0] == 2) {
                asks.push_back(make_pair(q[i][2], i));
            }
        }
        sort(rall(asks));
        int pos = 0;
        DSU dsu;
        dsu.build(n);
        for (int i = 0; i < (int)asks.size(); i += 1) {
            int f = asks[i].first;
            while (pos < (int)cnst_edgs.size() && cnst_edgs[pos].first >= f) {
                int t = cnst_edgs[pos].second;
                dsu.merge(e[t].first, e[t].second, false);
                pos += 1;
            }
            for (auto t : nt_cnst) {
                nd[t] = d[t];
            }
            for (int j = l; j <= asks[i].second; j += 1) {
                if (q[j][0] == 1) {
                    nd[q[j][1]] = q[j][2];
                }
            }
            for (auto t : nt_cnst) {
                if (nd[t] >= f) {
                    dsu.merge(e[t].first, e[t].second, true);
                }
            }
            rs[asks[i].second] = dsu.get_size(q[asks[i].second][1]);
            dsu.back();
        }
        for (int i = l; i < r; i += 1) {
            if (q[i][0] == 1) {
                d[q[i][1]] = q[i][2];
            }
        }
        vector<pair<ll, int>> new_edgs;
        for (auto t : nt_cnst) {
            new_edgs.push_back(make_pair(d[t], t));
        }
        sort(rall(new_edgs));
        merge(all(cnst_edgs), all(new_edgs), all_sorted.begin(), comp);
    }
    for (int i = 0; i < qs; i += 1) {
        if (q[i][0] == 2) {
            cout << rs[i] << "\n";
        }
    }
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int32_t main()':
bridges.cpp:120:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |         for (auto [_, i] : all_sorted) {
      |                   ^

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