Submission #336338

#	Time	Username	Problem	Language	Result	Execution time	Memory
336338		12tqian	Bridges (APIO19_bridges)	C++17	73 / 100	3026 ms	10232 KiB

bridges

#include <bits/stdc++.h>

struct DSU {
    std::vector<int> e;
    void init(int n) {
        e = std::vector<int>(n, -1);
    }
    int get(int x) {
        return e[x] < 0 ? x : e[x] = get(e[x]);
    }
    bool same_set(int a, int b) {
        return get(a) == get(b);
    }
    int size(int x) {
        return -e[get(x)];
    }
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;
        if (e[x] > e[y]) std::swap(x, y);
        e[x] += e[y]; e[y] = x;
        return true;
    }
};
namespace output {
    using namespace std;
    void pr(int x) { cout << x; }
    void pr(long x) { cout << x; }
    // void pr(ll x) { cout << x; }
    void pr(unsigned x) { cout << x; }
    void pr(unsigned long x) { cout << x; }
    void pr(unsigned long long x) { cout << x; }
    void pr(float x) { cout << x; }
    void pr(double x) { cout << x; }
    // void pr(ld x) { cout << x; }
    void pr(char x) { cout << x; }
    void pr(const char* x) { cout << x; }
    void pr(const string& x) { cout << x; }
    void pr(bool x) { pr(x ? "true" : "false"); }
    template<class T> void pr(const complex<T>& x) { cout << x; }
    template<class T1, class T2> void pr(const pair<T1, T2>& x);
    template<class T> void pr(const T& x);
    template<class T, class... Ts> void pr(const T& t, const Ts&... ts) {
        pr(t); pr(ts...); }
    template<class T1, class T2> void pr(const pair<T1,T2>& x) {
        pr("{", x.f, ", ", x.s, "}"); }
    template<class T> void pr(const T& x) {
        pr("{"); // const iterator needed for vector<bool>
        bool fst = 1; for (const auto& a: x) pr(!fst ? ", " : "", a), fst = 0;
        pr("}"); }
    void ps() { pr("\n"); } // print w/ spaces
    template<class T, class... Ts> void ps(const T& t, const Ts&... ts) {
        pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); }
    void pc() { pr("]\n"); } // debug w/ commas
    template<class T, class... Ts> void pc(const T& t, const Ts&... ts) {
        pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); }
}


using namespace output;
int main() {
    const int B = 800;
    const int INF = 1e9;
    using namespace std;
    ios_base::sync_with_stdio(0);
    int n, m; cin >> n >> m;
    vector<vector<int>> adj(n);
    vector<array<int, 3>> ed;
    vector<int> id(m);
    iota(id.begin(), id.end(), 0);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        u--, v--;
        ed.push_back({u, v, w});
    }
    
    vector<int> mod(m);
    int q; cin >> q;
    vector<array<int, 3>> modify;
    vector<array<int, 3>> queries;
    vector<int> vis(n);
    vector<int> rem;
    vector<array<int, 2>> ans;
    vector<int> change(m, -1);
    vector<int> todo;
    DSU D;
    for (int i = 0; i < q; i++) {
        int x, y, z; cin >> x >> y >> z;
        y--;
        if (x == 1) 
            modify.push_back({y, z, i});
        else 
            queries.push_back({y, z, i});
        if (i == q - 1 || int(modify.size()) + int(queries.size()) == B) {
            sort(id.begin(), id.end(), [&ed](int& x, int & y) {
                return ed[x][2] < ed[y][2];
            }); 
            D.init(n);
            sort(queries.begin(), queries.end(), [](array<int, 3>& a, array<int, 3>& b) {
                return a[1] > b[1];
            });
            for (auto& mm : modify) 
                mod[mm[0]] = 1;
            int it = m;
            for (auto& qq : queries) {
                int weight = qq[1];
                int ti = qq[2];
                while (it && ed[id[it - 1]][2] >= weight) {
                    it--;
                    if (!mod[id[it]]) 
                        D.unite(ed[id[it]][0], ed[id[it]][1]);
                }
                for (auto& mm : modify) { 
                    todo.push_back(mm[0]);
                    if (mm[2] < ti) 
                        change[mm[0]] = mm[1];
                }
                for (auto& t : todo) {
                    if (change[t] == -1) {
                        if (ed[t][2] >= weight) {
                            int u = D.get(ed[t][0]);
                            int v = D.get(ed[t][1]);
                            adj[u].push_back(v);
                            adj[v].push_back(u);
                        }
                    } else {
                        if (change[t] >= weight) {
                            int u = D.get(ed[t][0]);
                            int v = D.get(ed[t][1]);
                            adj[u].push_back(v);
                            adj[v].push_back(u);
                        }
                    }
                }
                int res = 0;
                function<void(int)> dfs = [&](int src) {
                    vis[src] = 1;
                    res += D.size(src);
                    rem.push_back(src);
                    for (int nxt : adj[src]) {
                        if (vis[nxt])
                            continue;
                        dfs(nxt);
                    }
                };
                dfs(D.get(qq[0]));
                ans.push_back({ti, res});
                for (auto& r : rem)
                    vis[r] = 0;
                for (auto& t : todo) 
                    change[t] = -1;
                for (auto& t : todo) {
                    int u = D.get(ed[t][0]);
                    int v = D.get(ed[t][1]);
                    adj[u].clear();
                    adj[v].clear();
                }
                rem.clear();
                todo.clear();
            }
            for (auto& mm : modify)
                mod[mm[0]] = 0, ed[mm[0]][2] = mm[1];
            queries.clear();
            modify.clear();
        }
    }
    sort(ans.begin(), ans.end());
    for (auto& a : ans) 
        cout << a[1] << '\n';
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:63:15: warning: unused variable 'INF' [-Wunused-variable]
   63 |     const int INF = 1e9;
      |               ^~~

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