Submission #527721

#	Time	Username	Problem	Language	Result	Execution time	Memory
527721		Olympia	Bridges (APIO19_bridges)	C++17	13 / 100	3085 ms	29868 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>

using namespace std;
class DisjointSetUnion {
private:
    vector<int> parent;
    vector<int> compSize;
    int n;
    int connectedComponents;
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) {
        x = find_head(x);
        y = find_head(y);
        if (x == y) {
            return;
        }
        if (compSize[x] > compSize[y]) {
            swap(x, y);
            //ensures that compSize[x1] <= compSize[y1]
        }
        parent[x] = y;
        compSize[y] += compSize[x];
        connectedComponents--;
    }

    bool comp(int x, int y) {
        return (find_head(x) == find_head(y));
    }
};
class Query {
public:
    int w;
    int x;
    int type;
    int q;
    //w is hte weight thing
    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);
}
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));
    }
    map<int,int> default_edges;
    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);
        set<int> uncertain;
        set<pair<int,int>> unknown[M];
        for (Query q: v) {
            if (q.type == 1) {
                uncertain.insert(q.x);
                unknown[q.x].insert({q.q, q.w});
            }
        }
        for (auto& p: default_edges) {
            unknown[p.first].insert({-1, p.second});
        }
        map<int,vector<int>> e;
        for (int i = 0; i < M; i++) {
            if (!uncertain.count(i)) {
                e[default_edges[i]].push_back(i);
            }
        }
        reverse(v.begin(), v.end());
        for (Query q: v) {
            for (auto it = e.lower_bound(q.w); it != e.end(); it++) {
                for (int i: (*it).second) {
                    dsu.join(edges[i].first.first, edges[i].first.second);
                }
            }
            if (q.type == 1) {
                continue;
            }
            DisjointSetUnion prev_dsu = dsu;
            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);
                }
            }
            myVec.push_back({q.q, dsu.getNeighbors(q.x)});
            dsu = prev_dsu;
        }
        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';
    }
}

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