Submission #376915

#	Time	Username	Problem	Language	Result	Execution time	Memory
376915		KoD	Bridges (APIO19_bridges)	C++17	100 / 100	2314 ms	4552 KiB

bridges

#include <bits/stdc++.h>
 
template <class T>
using Vec = std::vector<T>;
 
struct DSU {
    Vec<int> par;
    std::stack<std::pair<int, int>> past;
    DSU(const int n): par(n, -1) { }
    int find(int u) const {
        while (par[u] >= 0) {
            u = par[u];
        }
        return u;
    }
    int find_notrack(const int u) {
        return par[u] < 0 ? u : par[u] = find_notrack(par[u]);
    }
    int merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return 0;
        }
        if (par[x] > par[y]) {
            std::swap(x, y);
        }
        past.emplace(x, par[x]);
        past.emplace(y, par[y]);
        par[x] += par[y];
        par[y] = x;
        return 2;
    }
    void merge_notrack(int x, int y) {
        x = find_notrack(x);
        y = find_notrack(y);
        if (x == y) {
            return;
        }
        if (par[x] > par[y]) {
            std::swap(x, y);
        }
        par[x] += par[y];
        par[y] = x;
    }
    int comp(const int x) const {
        return -par[find(x)];
    }
    void rollback() {
        while (!past.empty()) {
            const auto [i, v] = past.top();
            past.pop();
            par[i] = v;
        }
    }
};
 
int scan() {
    int x;
    std::scanf("%d", &x);
    return x;
}
 
constexpr int BSIZE = 800;
 
int main() {
    const auto N = scan();
    const auto M = scan();
    Vec<int> U(M), V(M), D(M);
    for (int i = 0; i < M; ++i) {
        U[i] = scan() - 1;
        V[i] = scan() - 1;
        D[i] = scan();
    }
    const auto Q = scan();
    Vec<int> T(Q), K(Q), W(Q);
    for (int i = 0; i < Q; ++i) {
        T[i] = scan();
        K[i] = scan() - 1;
        W[i] = scan();
    }
    const auto Steps = (Q + BSIZE - 1) / BSIZE;
    Vec<int> ans;
    ans.reserve(Q);
    Vec<bool> dyn(M);
    Vec<int> still(M);
    std::iota(still.begin(), still.end(), 0);
    for (int step = 0; step < Steps; ++step) {
        const auto qL = step * BSIZE;
        const auto qR = std::min((step + 1) * BSIZE, Q);
        Vec<int> set;
        Vec<std::pair<int, int>> ask;
        set.reserve(qR - qL);
        ask.reserve(qR - qL);
        for (int i = qL; i < qR; ++i) {
            if (T[i] == 1) {
                set.push_back(i);
                dyn[K[i]] = true;
            }
            else {
                ask.emplace_back(i, (int) ans.size());
                ans.push_back(0);
            }
        }
        std::sort(ask.begin(), ask.end(), [&](const auto &q1, const auto &q2) {
            return W[q1.first] > W[q2.first];
        });
        Vec<int> change;
        change.reserve(qR - qL);
        for (int i = 0; i < M; ++i) {
            if (dyn[i]) {
                change.push_back(i);
            }
        }
        std::sort(still.begin(), still.end(), [&](const int i, const int j) {
            return D[i] < D[j];
        });
        DSU dsu(N);
        int still_idx = (int) still.size();
        for (const auto [idx, ptr]: ask) {
            while (still_idx > 0) {
                const auto i = still[still_idx - 1];
                if (dyn[i]) {
                    still_idx -= 1;
                    continue;
                }
                if (W[idx] > D[i]) {
                    break;
                }
                still_idx -= 1;
                dsu.merge_notrack(U[i], V[i]);
            }
            std::stack<std::pair<int, int>> past;
            for (const auto i: set) {
                if (i > idx) {
                    break;
                }
                past.emplace(K[i], D[K[i]]);
                D[K[i]] = W[i];
            }
            for (const auto i: change) {
                if (W[idx] <= D[i]) {
                    dsu.merge(U[i], V[i]);
                }
            }
            ans[ptr] = dsu.comp(K[idx]);
            dsu.rollback();
            while (!past.empty()) {
                const auto [i, v] = past.top();
                past.pop();
                D[i] = v;
            }
        }
        for (const auto i: set) {
            D[K[i]] = W[i];
            dyn[K[i]] = false;
        }
    }
    for (const auto x: ans) {
        std::printf("%d\n", x);
    }
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int scan()':
bridges.cpp:60:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |     std::scanf("%d", &x);
      |     ~~~~~~~~~~^~~~~~~~~~

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