Submission #860068

#	Time	Username	Problem	Language	Result	Execution time	Memory
860068		TahirAliyev	Bridges (APIO19_bridges)	C++17	100 / 100	1607 ms	9712 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>

const int MAX = 1e5 + 5, BLOCK = 1000;

struct E{
    int a, b, w, id;
};

int par[MAX];
vector<array<int, 4>> op;

int get(int node){
    if(par[node] < 0){
        return node;
    }
    return get(par[node]);
}

void unite(int u, int v, bool tolist = false){
    u = get(u), v = get(v);
    if(u == v) return;
    if(-par[u] < -par[v]){
        swap(u, v);
    }
    if(tolist){
        op.push_back({u, v, par[u], par[v]});
    }
    par[u] += par[v];
    par[v] = u;
}

void rollback(){
    while(!op.empty()){
        array<int, 4> a = op.back();
        op.pop_back();
        par[a[0]] = a[2];
        par[a[1]] = a[3];
    }
}

int n, m, q;

vector<E> edges;
array<int, 3> queries[MAX];
int ans[MAX];

vector<E> ed;
vector<array<int, 3>> s;
vector<int> updated[MAX];
vector<int> updates;

bool comp(E a, E b){
    return a.w < b.w;
}

void clean(){
    memset(par, -1, sizeof(par));
    for(int a:updates){
        updated[a].clear();
    }
    updates.clear();
    ed = edges;
    op.clear();
    s.clear();
    sort(ed.rbegin(), ed.rend(), comp);
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        E e;
        cin >> e.a >> e.b >> e.w;
        e.id = i;
        edges.push_back(e);
    }
    cin >> q;
    for(int i = 1; i <= q; i++){
        cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
    }

    for(int i = 1; i <= q; i += BLOCK){
        clean();
        for(int j = i; j <= i + BLOCK - 1 && j <= q; j++){
            if(queries[j][0] == 2){
                s.push_back({queries[j][2], queries[j][1], j});
            }
            else{
                if(updated[queries[j][1]].empty()){
                    updates.push_back(queries[j][1]);
                }
                updated[queries[j][1]].push_back(j);
            }
        }

        sort(s.rbegin(), s.rend());
        auto itr = ed.begin();
        for(auto a : s){
            while(itr != ed.end() && itr->w >= a[0]){
                if(updated[itr->id].empty()){
                    unite(itr->a, itr->b);
                }
                itr++;
            }
            for(int p : updates){
                int b = -1;
                for(int u : updated[p]){
                    if(u < a[2]){
                        b = u;
                    }
                    else{
                        break;
                    }
                }
                if(b == -1){
                    if(edges[p - 1].w >= a[0]){
                        unite(edges[p - 1].a, edges[p - 1].b, 1);
                    }
                }
                else{
                    if(queries[b][2] >= a[0]){
                        unite(edges[p - 1].a, edges[p - 1].b, 1);
                    }
                }
            }
            ans[a[2]] = -par[get(a[1])];
            rollback();
        }
        for(int u : updates){
            edges[u - 1].w = queries[updated[u].back()][2];
        }
    }

    for(int i = 1; i <= q; i++){
        if(queries[i][0] == 1) continue; 
        cout << ans[i] << '\n';
    }
}

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