oj.uz

Submission #137299

# Submission time Handle Problem Language Result Execution time Memory
137299 2019-07-27T12:29:51 Z mlyean00 Bridges (APIO19_bridges) C++17
13 / 100
 3000 ms 4436 KB 
#include <bits/stdc++.h>

using namespace std;

struct disjoint_set {
    vector<int> parent, sz;

    disjoint_set(int n) : parent(n), sz(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int u) {
        if (u != parent[u]) u = find(parent[u]);
        return parent[u];
    }

    void merge(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        if (sz[u] > sz[v]) swap(u, v);
        parent[u] = v;
        sz[v] += sz[u];
    }
};

struct query_1 {
    int t;
    int b, r;

    query_1(int t, int b, int r) : t(t), b(b), r(r) {}
};

struct query_2 {
    int t;
    int s, w;
    int ans = 0;

    query_2(int t, int s, int w) : t(t), s(s), w(w) {}

    bool operator<(query_2 const& other) {
        return w < other.w;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<int> u(m), v(m), d(m);
    for (int i = 0; i < m; ++i) {
        cin >> u[i] >> v[i] >> d[i];
        --u[i], --v[i];
    }

    int q;
    cin >> q;

    /* int blk_sz = ceil(sqrt(q)); */
    /* int blk_sz = q; */
    int blk_sz = 1;

    for (int i = 0; i < q; i += blk_sz) {
        vector<query_1> qu1;
        vector<query_2> qu2;
        for (int j = 0; j < min(blk_sz, q - i); ++j) {
            int t;
            cin >> t;
            if (t == 1) {
                int b, r;
                cin >> b >> r;
                --b;
                qu1.emplace_back(j, b, r);
                // Invalidate bridge
                d[b] = -abs(d[b]);
            } else if (t == 2) {
                int s, w;
                cin >> s >> w;
                --s;
                qu2.emplace_back(j, s, w);
            }
        }
        sort(qu2.rbegin(), qu2.rend());

        // Answer type 2 queries
        disjoint_set ds(n);
        for (query_2& q2 : qu2) {
            for (int j = 0; j < m; ++j) {
                if (d[j] >= q2.w) ds.merge(u[j], v[j]);
            }

            vector<pair<int, int>> edges;
            int src = ds.find(q2.s);
            vector<int> c {src};

            for (query_1 const& q1 : qu1) {
                if (q1.t <= q2.t) {
                    if (q1.r < q2.w) continue;
                    int u0 = ds.find(u[q1.b]);
                    int v0 = ds.find(v[q1.b]);
                    if (u0 != v0) {
                        edges.emplace_back(u0, v0);
                        c.push_back(u0);
                        c.push_back(v0);
                    }
                } else {
                    assert(d[q1.b] < 0);
                    if (-d[q1.b] < q2.w) continue;
                    int u0 = ds.find(u[q1.b]);
                    int v0 = ds.find(v[q1.b]);
                    if (u0 != v0) {
                        edges.emplace_back(u0, v0);
                        c.push_back(u0);
                        c.push_back(v0);
                    }
                }
            }

            // Coordinate compression
            sort(c.begin(), c.end());
            c.erase(unique(c.begin(), c.end()), c.end());
            src = lower_bound(c.begin(), c.end(), src) - c.begin();

            // Graph construction
            vector<vector<int>> g(c.size());
            for (auto [u0, v0] : edges) {
                int u1 = lower_bound(c.begin(), c.end(), u0) - c.begin();
                int v1 = lower_bound(c.begin(), c.end(), v0) - c.begin();
                g[u1].push_back(v1);
                g[v1].push_back(u1);
            }

            // DFS
            stack<int> st;
            vector<bool> visited(g.size());

            st.push(src);
            visited[src] = true;

            while (!st.empty()) {
                int u0 = st.top();
                st.pop();
                for (int v0 : g[u0]) {
                    if (visited[v0]) continue;
                    visited[v0] = true;
                    st.push(v0);
                }
            }

            for (int j = 0; j < g.size(); ++j) {
                if (!visited[j]) continue;
                q2.ans += ds.sz[c[j]];
            }
        }

        // Apply changes from type 1 queries
        for (query_1 const& q1 : qu1) {
            d[q1.b] = q1.r;
        }

        // Print answers to type 2 queries
        sort(qu2.begin(), qu2.end(),
             [](query_2 const& q1, query_2 const& q2) { return q1.t < q2.t; });

        for (query_2 const& q2 : qu2) {
            cout << q2.ans << endl;
        }
    }

    return 0;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:153:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < g.size(); ++j) {
                             ~~^~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 92 ms 504 KB Output is correct
4 Correct 36 ms 504 KB Output is correct
5 Correct 26 ms 632 KB Output is correct
6 Correct 24 ms 532 KB Output is correct
7 Correct 29 ms 504 KB Output is correct
8 Correct 29 ms 508 KB Output is correct
9 Correct 31 ms 504 KB Output is correct
10 Correct 30 ms 504 KB Output is correct
11 Correct 30 ms 504 KB Output is correct
12 Correct 30 ms 504 KB Output is correct
13 Correct 33 ms 504 KB Output is correct
14 Correct 33 ms 504 KB Output is correct
15 Correct 34 ms 504 KB Output is correct
16 Correct 31 ms 504 KB Output is correct
17 Correct 29 ms 504 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3036 ms 3052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3048 ms 2316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3058 ms 4436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3036 ms 3052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 92 ms 504 KB Output is correct
4 Correct 36 ms 504 KB Output is correct
5 Correct 26 ms 632 KB Output is correct
6 Correct 24 ms 532 KB Output is correct
7 Correct 29 ms 504 KB Output is correct
8 Correct 29 ms 508 KB Output is correct
9 Correct 31 ms 504 KB Output is correct
10 Correct 30 ms 504 KB Output is correct
11 Correct 30 ms 504 KB Output is correct
12 Correct 30 ms 504 KB Output is correct
13 Correct 33 ms 504 KB Output is correct
14 Correct 33 ms 504 KB Output is correct
15 Correct 34 ms 504 KB Output is correct
16 Correct 31 ms 504 KB Output is correct
17 Correct 29 ms 504 KB Output is correct
18 Execution timed out 3036 ms 3052 KB Time limit exceeded
19 Halted 0 ms 0 KB -