Submission #975796

#	Time	Username	Problem	Language	Result	Execution time	Memory
975796		Unforgettablepl	Bridges (APIO19_bridges)	C++17	100 / 100	2564 ms	15176 KiB

bridges

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int sqrtq = 500;

struct UFDS {
    vector<int> p, sz;
    // stores previous unites
    vector<pair<int &, int>> history;
    UFDS(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }

    int get(int x) { return x == p[x] ? x : get(p[x]); }

    void unite(int a, int b) {
        a = get(a);
        b = get(b);
        if (a == b) { return; }
        if (sz[a] < sz[b]) { swap(a, b); }

        // save this unite operation
        history.emplace_back(sz[a], sz[a]);
        history.emplace_back(p[b], p[b]);

        p[b] = a;
        sz[a] += sz[b];
    }

    int snapshot() const { return history.size(); }

    void rollback(int until) {
        while (snapshot() > until) {
            history.back().first = history.back().second;
            history.pop_back();
        }
    }
};

pair<int,pair<int,int>> edgelist[100001];
int n,m;

void answer(vector<pair<int,pair<int,int>>> &updates,vector<tuple<int,int,int>> &queries){
    set<int> updated;
    for(auto&i:updates)updated.insert(i.second.first);
    vector<pair<int,pair<int,int>>> edges;
    for(int i=1;i<=m;i++)if(updated.count(i)==0)edges.emplace_back(edgelist[i]);
    sort(edges.rbegin(),edges.rend());
    sort(queries.rbegin(),queries.rend());
    sort(updates.begin(), updates.end(),[](pair<int,pair<int,int>> a, pair<int,pair<int,int>> b){
        return a.second.first==b.second.first ? a.first<b.first : a.second.first<b.second.first;
    });
    auto iter = edges.begin();
    UFDS dsu(50001);
    vector<pair<int,int>> ans;
    for(auto[wt,tim,pos]:queries){
        while(iter!=edges.end() and iter->first>=wt){dsu.unite(iter->second.first,iter->second.second);iter++;}
        int snap = dsu.snapshot();
        for(int i=0;i<updates.size();i++){
            if(i!=updates.size()-1 and updates[i].second.first==updates[i+1].second.first and updates[i+1].first<tim)continue;
            if(i!=0 and updates[i].second.first==updates[i-1].second.first and updates[i].first>tim)continue;
            auto [timu,up] = updates[i];
            if((timu<tim and up.second>=wt) or (tim<timu and edgelist[up.first].first>=wt))dsu.unite(edgelist[up.first].second.first,edgelist[up.first].second.second);
        }
        ans.emplace_back(tim,dsu.sz[dsu.get(pos)]);
        dsu.rollback(snap);
    }
    for(auto[tim,up]:updates)edgelist[up.first].first=up.second;
    sort(ans.begin(), ans.end());
    for(auto[tim,an]:ans)cout<<an<<'\n';
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i=1;i<=m;i++)cin>>edgelist[i].second.first>>edgelist[i].second.second>>edgelist[i].first;
    int q;
    cin >> q;
    int curr = 0;
    vector<pair<int,pair<int,int>>> updates;
    vector<tuple<int,int,int>> queries;
    for(int i=1;i<=q;i++){
        int type,a,b;cin>>type>>a>>b;
        if(type==1){
            updates.emplace_back(i,make_pair(a,b));
            curr++;
        } else {
            queries.emplace_back(b,i,a);
        }
        if(curr==sqrtq){
            answer(updates,queries);
            updates.clear();
            queries.clear();
            curr=0;
        }
    }
    answer(updates,queries);
}

Compilation message (stderr)

bridges.cpp: In function 'void answer(std::vector<std::pair<long long int, std::pair<long long int, long long int> > >&, std::vector<std::tuple<long long int, long long int, long long int> >&)':
bridges.cpp:60:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for(int i=0;i<updates.size();i++){
      |                     ~^~~~~~~~~~~~~~~
bridges.cpp:61:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             if(i!=updates.size()-1 and updates[i].second.first==updates[i+1].second.first and updates[i+1].first<tim)continue;
      |                ~^~~~~~~~~~~~~~~~~~

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