Submission #788148

#	Time	Username	Problem	Language	Result	Execution time	Memory
788148		PanosPask	Bridges (APIO19_bridges)	C++14	0 / 100	3016 ms	9772 KiB

bridges

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair

using namespace std;

typedef pair<int, int> pi;

struct DSU {
    int size;
    vector<int> rep;
    vector<int> sz;
    stack<pi> size_updates;
    stack<pi> rep_updates;

    void init(int n) {
        size = n;
        sz.assign(size, 1);
        while (!size_updates.empty())
            size_updates.pop();
        while (!rep_updates.empty())
            rep_updates.pop();

        rep.resize(size);
        for (int i = 0; i < n; i++)
            rep[i] = i;
    }
    void clear(void) {
        init(size);
    }

    void save(void) {
        size_updates.push(mp(-1, -1));
        rep_updates.push(mp(-1, -1));
    }
    void rollback(void) {
        while (size_updates.top().first != -1) {
            sz[size_updates.top().first] = size_updates.top().second;
            size_updates.pop();
        }
        size_updates.pop();
        while (rep_updates.top().first != -1) {
            rep[rep_updates.top().first] = rep_updates.top().second;
            rep_updates.pop();
        }
        rep_updates.pop();
    }

    int find(int a) {
        if (rep[a] != a)
            return find(rep[a]);

        return rep[a];
    }
    bool same(int a, int b) {
        return find(a) == find(b);
    }
    int component(int a) {
        return sz[find(a)];
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b)
            return;

        if (sz[a] < sz[b])
            swap(a, b);

        size_updates.push(mp(a, sz[a]));
        rep_updates.push(mp(b, b));
        sz[a] += sz[b];
        rep[b] = a;

        return;
    }
};

struct Edge {
    int a, b, w;
    int id;

    bool operator < (const Edge& b) {
        return this->w < b.w;
    }
};
struct Update {
    int edge;
    int v;
    int time;

    bool operator < (const Update& b) {
        return this->time > b.time;
    }
};
struct Query {
    int id;
    int s;
    int v;
    int time;

    bool operator < (const Query& b) {
        return this->v < b.v;
    }
};

int N, M, Q;
int BLOCK_SIZE;
vector<Edge> edges;
vector<Edge> original_edges;
vector<bool> changed;
vector<int> ans;

DSU graph;

void process_block(vector<Update>& updates, vector<Query>& queries)
{
    graph.clear();
    changed.assign(M, false);

    sort(queries.rbegin(), queries.rend());
    sort(updates.rbegin(), updates.rend());
    for (auto u : updates) {
        changed[u.edge] = true;
    }

    int cure = 0;
    for (auto& q : queries) {
        while (cure < M && edges[cure].w >= q.v) {
            if (!changed[edges[cure].id])
                graph.unite(edges[cure].a, edges[cure].b);

            cure++;
        }

        graph.save();
        for (auto& u : updates) {
            if (u.time > q.time)
                continue;
            if (!changed[u.edge])
                continue;

            // mark this edge
            changed[u.edge] = false;
            if (u.v < q.v)
                continue;

            int a = original_edges[u.edge].a;
            int b = original_edges[u.edge].b;
            graph.unite(a, b);
        }
        for (auto& u : updates) {
            if (u.time < q.time)
                break;
            if (!changed[u.edge])
                continue;

            changed[u.edge] = false;
            int a, b, v;
            a = original_edges[u.edge].a;
            b = original_edges[u.edge].b;
            v = original_edges[u.edge].w;

            if (v < q.v)
                continue;
            graph.unite(a, b);
        }
        for (auto& u : updates) {
            changed[u.edge] = true;
        }

        ans[q.id] = graph.component(q.s);
        graph.rollback();
    }
}

int main(void)
{
    scanf("%d %d", &N, &M);

    changed.resize(M);
    graph.init(N);

    for (int i = 0; i < M; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        u--; v--;

        edges.push_back({u, v, w, i});
        original_edges.push_back({u, v, w, i});
    }
    edges = original_edges;
    sort(edges.rbegin(), edges.rend());

    scanf("%d", &Q);

    BLOCK_SIZE = sqrt(Q);
    vector<Query> queries;
    vector<Update> updates;
    for (int i = 0; i < Q; i++) {
        int op;
        scanf("%d", &op);

        if (op == 1) {
            int id, v;
            scanf("%d %d", &id, &v);
            id--;

            updates.push_back({id, v, i});
        }
        else {
            int s, v;
            scanf("%d %d", &s, &v);
            s--;

            queries.push_back({(int)ans.size(), s, v, i});
            ans.push_back({0});
        }

        if (!((i + 1) % BLOCK_SIZE)) {
            process_block(updates, queries);

            for (auto& u : updates) {
                original_edges[u.edge].w = u.v;
            }
            edges = original_edges;
            sort(edges.rbegin(), edges.rend());

            updates.clear();
            queries.clear();
        }
    }
    process_block(updates, queries);

    for (int i = 0; i < ans.size(); i++) {
        printf("%d\n", ans[i]);
    }

    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:237:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  237 |     for (int i = 0; i < ans.size(); i++) {
      |                     ~~^~~~~~~~~~~~
bridges.cpp:181:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |     scanf("%d %d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:188:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |         scanf("%d %d %d", &u, &v, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:197:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  197 |     scanf("%d", &Q);
      |     ~~~~~^~~~~~~~~~
bridges.cpp:204:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |         scanf("%d", &op);
      |         ~~~~~^~~~~~~~~~~
bridges.cpp:208:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  208 |             scanf("%d %d", &id, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~~~
bridges.cpp:215:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  215 |             scanf("%d %d", &s, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~~

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