Submission #1230180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230180		Adomas08	Bridges (APIO19_bridges)	C++20	0 / 100	3092 ms	7348 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

int parent[50000], sizes[50000];
vector<pair<int &, int>> history;
int trueparent(int n){
    if (parent[n] == n) return n;
    else return (trueparent(parent[n]));
}
void unite (int x, int y){
    int a = trueparent(x), b = trueparent(y);
    if (a == b) return;
    if (sizes[a] > sizes[b]){
    }
    else{
        swap(a, b);
    }
    history.push_back({sizes[a], sizes[a]});
    history.push_back({parent[b], parent[b]});
    parent[b] = a;
    sizes[a] += sizes[b];
}
struct pair_hash {
    std::size_t operator() (const std::pair<int,int> &p) const {
        // A simple but decent hash combiner
        return std::hash<int>()(p.first) ^ (std::hash<int>()(p.second) << 1);
    }
};
bool greaterse(pair<pair<int, int>, pair<int, int>> x, pair<pair<int, int>, pair<int, int>> y){
    return x.first.first > y.first.first;
}
bool gretersee(pair<pair<int, int>, pair<int, int>> x, pair<pair<int, int>, pair<int, int>> y){
    return x.first.first < y.first.first;
}
bool gretersew(pair<pair<int, int>, pair<int, int>> x, pair<pair<int, int>, pair<int, int>> y){
    return x.first.second < y.first.second;
}
int main(){
    int n, m;
    cin >> n >> m;
    vector <pair<int, int>> adj[n];
    vector <pair<pair<int, int>, pair<int, int>>> roads;
    for (int i = 0; i < m; i++){
        int x, y, z;
        cin >> x >> y >> z;
        x--;
        y--;

        if (y > x) swap(x, y);
        adj[x].push_back({y, z});
        adj[y].push_back({x, z});
        roads.push_back({{z, i}, {x, y}});
    } 
    int q;
    cin >> q;
    int k = sqrt(q);
    for (int i = 0; i < q; i += k){
        bool visited[m];
        for (int j = 0; j < n; j++){
            sizes[j] = 1;
            parent[j] = j;
        }
        for (int j = 0; j < m; j++) visited[j] = 0;
        int start = i, e = min(q - 1, i + k - 1);
        vector <pair<pair<int, int>, pair<int, int>>> quirky;
        vector <pair<pair<int, int>,pair<int , int>>> calculations;
        for (int j = start; j <= e; j++){
            int x, y, z;
            cin >> x >> y >> z;
            y--;
            if (x == 2){
                calculations.push_back({{z, j}, {y, calculations.size()}});
            }
            else{
                if (!visited[y]) quirky.push_back({{-1, roads[y].first.first}, {roads[y].second.first, roads[y].second.second}});
                quirky.push_back({{j, z}, {roads[y].second.first, roads[y].second.second}});
                visited[y] = 1;
                roads[y].first.first = 0;
            }
        }
        sort(roads.begin(), roads.end(), greaterse);
        sort (calculations.begin(), calculations.end(), greaterse);
        sort (quirky.begin(), quirky.end(), gretersee);
        vector <int> ans (calculations.size());
        int prew = 0;
        for (auto f : calculations){
            int amo = 0;
            int cur = f.first.first;
            int s = f.first.second;
            while (prew != roads.size() && roads[prew].first.first >= cur){
            
                unite(roads[prew].second.first, roads[prew].second.second);
                prew++;
            }
            vector <pair<int, pair<int, int>>> badroads;
            history.clear();
            unordered_map <pair<int, int>, int, pair_hash> ms;
            for (auto u : quirky){
                if (u.first.first > s) break;
                ms[{u.second.first, u.second.second}] = u.first.second;
            }
            
            for (auto u : ms){
                if (u.second >= cur){
                    
                    unite(u.first.first, u.first.second);
                }
            }
            ans[f.second.second] = sizes[trueparent(f.second.first)];
            while (history.size() != 0){
                history.back().first = history.back().second;
                history.pop_back();
            }
            
        }
        for (auto u : ans) cout << u <<endl;
        vector <pair<int, pair<int, int>>> badroads;
        int s = INT_MAX;
        unordered_map <pair<int, int>, int, pair_hash> ms;
        for (auto u : quirky){
                if (u.first.first > s) break;
                ms[{u.second.first, u.second.second}] = u.first.second;
            }
        for (auto &v : roads){
            if (v.first.first != 0) continue;
            v.first.first = ms[{v.second.first, v.second.second}];
        }
        sort(roads.begin(), roads.end(), gretersew);
    }
}

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