Submission #527954

#	Time	Username	Problem	Language	Result	Execution time	Memory
527954		Olympia	Bridges (APIO19_bridges)	C++17	30 / 100	3098 ms	29404 KiB

bridges

#include <cmath>
#include <cassert>
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <type_traits>
#include <string>
#include <queue>
#include <map>
#include <stack>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("Ofast")
 
using namespace std;
 
class Updates {
public:
    int parentInd;
    int prev_parent;
    int compInd;
    int prev_comp;
    int cc;
};
 
class DisjointSetUnion {
private:
    vector<int> parent;
    vector<int> compSize;
    int n;
    int connectedComponents;
    stack<Updates> myStack;
public:
    int getConnectedComponents() const {
        return connectedComponents;
    }
 
    int getNeighbors(int x) {
        return compSize[find_head(x)];
    }
 
public:
    void resz(int sz) {
        n = sz;
        connectedComponents = sz;
        parent.resize(sz), compSize.resize(sz);
        for (int i = 0; i < n; i++) {
            parent[i] = i, compSize[i] = 1;
        }
    }
 
    int find_head(int x) const {
        int cur = x;
        while (cur != parent[cur]) {
            cur = parent[cur];
        }
        return cur;
    }
 
    void join(int x, int y, bool b) {
        x = find_head(x);
        y = find_head(y);
        if (x == y) {
            if (b) myStack.push({-1, -1, -1, -1, -1});
            return;
        }
        if (compSize[x] > compSize[y]) {
            swap(x, y);
        }
        if (b) myStack.push({x, parent[x], y, compSize[y], connectedComponents});
        parent[x] = y;
        compSize[y] += compSize[x];
        connectedComponents--;
    }
 
    void revert(int x) {
        while (x--) {
            Updates u = myStack.top();
            myStack.pop();
            if (u.prev_comp == -1) continue;
            parent[u.parentInd] = u.prev_parent;
            compSize[u.compInd] = u.prev_comp;
            connectedComponents = u.cc;
        }
    }
 
    bool comp(int x, int y) {
        return (find_head(x) == find_head(y));
    }
};
 
class Query {
public:
    int w;
    int x;
    short int type;
    int q;
 
    Query(int w, int x, int type, int q) {
        this->w = w, this->x = x, this->type = type, this->q = q;
    }
 
    bool operator<(const Query myQuery) const {
        if (myQuery.w != w) return (myQuery.w < w);
        if (myQuery.x != x) return (myQuery.x < x);
        if (myQuery.type != type) return (myQuery.type < type);
        return false;
    }
};
 
bool comp_index(Query a, Query b) {
    return (a.q < b.q);
}
 
void compress(vector<pair<pair<int, int>, int>> &edges, vector<vector<Query>> &blocks) {
    set<int> w;
    for (auto &p: edges) w.insert(p.second);
    for (auto &v: blocks) for (auto &q: v) w.insert(q.w);
    map<int, int> myMap;
    int cntr = 0;
    for (int i: w) {
        myMap[i] = cntr++;
    }
    for (int i = 0; i < edges.size(); i++) {
        edges[i].second = myMap[edges[i].second];
    }
    for (int i = 0; i < blocks.size(); i++) {
        for (int j = 0; j < blocks[i].size(); j++) {
            blocks[i][j].w = myMap[blocks[i][j].w];
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M;
    cin >> N >> M;
    vector<pair<pair<int, int>, int>> edges;
    for (int i = 0; i < M; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        x--, y--;
        edges.push_back({{x, y}, z});
    }
    int Q;
    cin >> Q;
    vector<vector<Query>> blocks;
    blocks.emplace_back();
    for (int i = 0; i < Q; i++) {
        if (blocks.back().size() > sqrt(Q)) {
            blocks.emplace_back();
        }
        int t, w, x;
        cin >> t >> x >> w;
        x--;
        blocks.back().emplace_back(Query(w, x, t, i));
    }
    compress(edges, blocks);
    int default_edges[M];
    for (int i = 0; i < M; i++) {
        default_edges[i] = edges[i].second;
    }
    vector<pair<int, int>> myVec;
    for (auto &v: blocks) {
        sort(v.begin(), v.end()); //sort the blocks by weight
        reverse(v.begin(), v.end());
        DisjointSetUnion dsu;
        dsu.resz(N);
        vector<int> uncertain;
        set<pair<int, int>> unknown[M];
        for (Query q: v) {
            if (q.type == 1) {
                uncertain.push_back(q.x);
                unknown[q.x].insert({q.q, q.w});
            }
        }
        for (int i = 0; i < M; i++) {
            unknown[i].insert({-1, default_edges[i]});
        }
        vector<vector<int>> e(M + Q);
        for (int i = 0; i < M; i++) {
            if (unknown[i].size() == 1) {
                e[default_edges[i]].push_back(i);
            }
        }
        reverse(v.begin(), v.end());
        int prev = e.size();
        for (Query &q: v) {
            for (int i = q.w; i < prev; i++) {
                for (int j: e[i]) {
                    dsu.join(edges[j].first.first, edges[j].first.second, 0);
                }
            }
            prev = q.w;
            if (q.type == 1) {
                continue;
            }
            int cntr = 0;
            for (int x: uncertain) {
                auto it = unknown[x].lower_bound({q.q + 1, -1});
                it--;
                int lastVal = (*it).second;
                if (lastVal >= q.w) {
                    dsu.join(edges[x].first.first, edges[x].first.second, 1);
                    cntr++;
                }
            }
            myVec.emplace_back(q.q, dsu.getNeighbors(q.x));
            dsu.revert(cntr);
        }
        sort(v.begin(), v.end(), comp_index);
        for (Query &q: v) {
            if (q.type == 1) {
                default_edges[q.x] = q.w;
            }
        }
    }
    sort(myVec.begin(), myVec.end());
    for (auto &p: myVec) {
        cout << p.second << '\n';
    }
}

Compilation message (stderr)

bridges.cpp:15: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   15 | #pragma GCC optimization ("O3")
      | 
bridges.cpp:16: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   16 | #pragma GCC optimization ("unroll-loops")
      | 
bridges.cpp:17: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   17 | #pragma GCC optimization ("Ofast")
      | 
bridges.cpp: In function 'void compress(std::vector<std::pair<std::pair<int, int>, int> >&, std::vector<std::vector<Query> >&)':
bridges.cpp:128:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for (int i = 0; i < edges.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
bridges.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<Query> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for (int i = 0; i < blocks.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
bridges.cpp:132:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         for (int j = 0; j < blocks[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~~

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