Submission #849447

#	Time	Username	Problem	Language	Result	Execution time	Memory
849447		ntkphong	Bridges (APIO19_bridges)	C++17	100 / 100	1623 ms	9012 KiB

bridges

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

const int mxN = 1e5 + 10;
const int BLOCK = 1000;

struct DSU {
    int lab[mxN];
    vector<pair<int, int>> q;
    
    void reset(int n) {
        q.clear();
        for(int i = 1; i <= n; i ++) lab[i] = -1;
    }
    
    int get_root(int u) {
        return lab[u] < 0 ? u : get_root(lab[u]);
    }
    
    bool unite(int u, int v) {
        u = get_root(u);
        v = get_root(v);
        
        if(u == v) return false;
        if(lab[u] > lab[v]) swap(u, v);
        
        q.push_back({v, lab[v]});
        q.push_back({u, lab[u]});
        
        lab[u] += lab[v];
        lab[v] = u;
           
        return true;
    }
    
    void roll_back(int x) {
        while(q.size() > x) {
            int u = q.back().first;
            int vu = q.back().second;
            lab[u] = vu;
            q.pop_back();
        }
    }
    
    int get_size(int u) {
        u = get_root(u);
        return - lab[u];
    }
} F;

int n, m, q;
int u[mxN], v[mxN], w[mxN];

int t[mxN], a[mxN], b[mxN];
bool changed[mxN];
int ans[mxN];

int main() {
    
    cin.tie(nullptr)->sync_with_stdio(false);
    
    cin >> n >> m;
    
    for(int i = 1; i <= m; i ++) 
        cin >> u[i] >> v[i] >> w[i];
    
    cin >> q;
    
    for(int i = 1; i <= q; i ++) 
        cin >> t[i] >> a[i] >> b[i];
    
    for(int block = 0; block < BLOCK; block ++) {
        int l = block * BLOCK + 1;
        int r = min((block + 1) * BLOCK, q);
        F.reset(n);
        
        if(l > r) break ;
        
        vector<int> changes, ask;
        vector<int> edges;
        vector<vector<pair<int, int>>> adj(BLOCK + 10);
        
        for(int i = l; i <= r; i ++) {
            if(t[i] == 1) {
                changed[a[i]] = true;
                changes.push_back(a[i]);
            } else 
                ask.push_back(i);
        }
    
        for(int i = 1; i <= m; i ++) {
            if(changed[i]) continue ;
            edges.push_back(i);
        }
                
        for(int i = l; i <= r; i ++) {
            if(t[i] == 1) w[a[i]] = b[i];
            else {
                for(int x : changes) {
                    adj[i - l].push_back({x, w[x]});
                }  
            }
        }
        
        sort(ask.begin(), ask.end(), [&](const int &x, const int &y) {
            return b[x] > b[y]; 
        });
        
        sort(edges.begin(), edges.end(), [&](const int &x, const int &y) {
            return w[x] > w[y]; 
        });
        
        for(int i = 0, j = 0; i < ask.size(); i ++) {
            for(; j < edges.size() && w[edges[j]] >= b[ask[i]]; j ++) 
                F.unite(u[edges[j]], v[edges[j]]); 
            
            int curr = F.q.size();
            for(auto [x, y] : adj[ask[i] - l]) {
                if(y < b[ask[i]]) continue ;
                F.unite(u[x], v[x]);
            }
            
            ans[ask[i]] = F.get_size(a[ask[i]]);
            F.roll_back(curr);
        }
        
        for(int x : changes) changed[x] = false;
    }
    
    for(int i = 1; i <= q; i ++) if(t[i] == 2) cout << ans[i] << "\n";
    return 0;
}

Compilation message (stderr)

bridges.cpp: In member function 'void DSU::roll_back(int)':
bridges.cpp:37:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |         while(q.size() > x) {
      |               ~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:113:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         for(int i = 0, j = 0; i < ask.size(); i ++) {
      |                               ~~^~~~~~~~~~~~
bridges.cpp:114:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             for(; j < edges.size() && w[edges[j]] >= b[ask[i]]; j ++)
      |                   ~~^~~~~~~~~~~~~~

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