Submission #1356100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1356100		srividya_06	Bridges (APIO19_bridges)	C++20	13 / 100	3095 ms	6024 KiB

bridges

                                                                                                                                                                                                                                                   
  #include <bits/stdc++.h>                                                                                                                                                                                                                          
  #define FOR(i, x, y) for (int i = x; i < y; i++)                                                                                                                                                                                                  
  using namespace std;                                                                                                                                                                                                                              
                                                                                                                                                                                                                                                    
  const int B = 1000;                                                                                                                                                                                                                               
                                                                                                                                                                                                                                                    
  int n, m, q;                                                                                                                                                                                                                                      
  int sz[100001], cmp[100001];
                                                                                                                                                                                                                                                    
  void reset() {                                                                                                                                                                                                                                    
      iota(cmp + 1, cmp + 1 + n, 1);                                                                                                                                                                                                                
      fill(sz + 1, sz + n + 1, 1);                                                                                                                                                                                                                  
  }                                                                                                                                                                                                                                                 
                                                                                                                                                                                                                                                    
  int find(int a) {                                                                                                                                                                                                                                 
      if (cmp[a] != a) cmp[a] = find(cmp[a]);  // Path compression OK
      return cmp[a];                                                                                                                                                                                                                                
  }                                                                                                                                                                                                                                                 
                                                                                                                                                                                                                                                    
  void unite(int a, int b) {                                                                                                                                                                                                                        
      a = find(a), b = find(b);
      if (a == b) return;                                                                                                                                                                                                                           
      if (sz[a] > sz[b]) swap(a, b);                                                                                                                                                                                                                
      sz[b] += sz[a];                                                                                                                                                                                                                               
      cmp[a] = b;                                                                                                                                                                                                                                   
  }                                                                                                                                                                                                                                                 
                                                                                                                                                                                                                                                    
  int u[100001], v[100001], w[100001];                                                                                                                                                                                                              
  int t[100001], x[100001], y[100001];
  bool changed[100001];                                                                                                                                                                                                                             
  int ans[100001];                                                                                                                                                                                                                                  
                                                                                                                                                                                                                                                    
  int dfs_count(int start, vector<vector<int>>& graph) {                                                                                                                                                                                            
      set<int> visited;
      stack<int> stk;                                                                                                                                                                                                                               
      stk.push(start);                                                                                                                                                                                                                              
      visited.insert(start);                                                                                                                                                                                                                        
                                                                                                                                                                                                                                                    
      int total = 0;                                                                                                                                                                                                                                
      while (!stk.empty()) {                                                                                                                                                                                                                        
          int node = stk.top(); stk.pop();                                                                                                                                                                                                          
          total += sz[node];                                                                                                                                                                                                                        
                                                                                                                                                                                                                                                    
          for (int neighbor : graph[node]) {                                                                                                                                                                                                        
              if (!visited.count(neighbor)) {                                                                                                                                                                                                       
                  visited.insert(neighbor);                                                                                                                                                                                                         
                  stk.push(neighbor);                                                                                                                                                                                                               
              }                                                                                                                                                                                                                                     
          }                                                                                                                                                                                                                                         
      }                                                                                                                                                                                                                                             
      return total;                                                                                                                                                                                                                                 
  }                                                                                                                                                                                                                                                 
                                                                                                                                                                                                                                                    
  int main() {                                                                                                                                                                                                                                      
      ios_base::sync_with_stdio(0);
      cin.tie(0);                                                                                                                                                                                                                                   
      cin >> n >> m;                                                                                                                                                                                                                                
      FOR(i, 1, m + 1) cin >> u[i] >> v[i] >> w[i];                                                                                                                                                                                                 
      cin >> q;                                                                                                                                                                                                                                     
      FOR(i, 1, q + 1) cin >> t[i] >> x[i] >> y[i];                                                                                                                                                                                                 
                                                                                                                                                                                                                                                    
      for (int l = 1; l <= q; l += B) {                                                                                                                                                                                                             
          int r = min(q + 1, l + B);                                                                                                                                                                                                                
          reset();                                                                                                                                                                                                                                  
          fill(changed + 1, changed + m + 1, false);                                                                                                                                                                                                
                                                                                                                                                                                                                                                    
          vector<int> ask, unchanged;                                                                                                                                                                                                               
          FOR(i, l, r) {                                                                                                                                                                                                                            
              if (t[i] == 1) changed[x[i]] = true;                                                                                                                                                                                                  
              else ask.push_back(i);                                                                                                                                                                                                                
          }                                                                                                                                                                                                                                         
          FOR(i, 1, m + 1) if (!changed[i]) unchanged.push_back(i);                                                                                                                                                                                 
                                                                                                                                                                                                                                                    
          // For each query, track which changed edges to use                                                                                                                                                                                       
          map<int, vector<int>> query_edges;  // query_edges[query_id] = list of edge IDs                                                                                                                                                           
                                                                                                                                                                                                                                                    
          FOR(query_id, l, r) {                                                                                                                                                                                                                     
              if (t[query_id] == 2) {                                                                                                                                                                                                               
                  // Track weight of changed edges at this query position                                                                                                                                                                           
                  map<int, int> edge_weight;                                                                                                                                                                                                        
                  FOR(e, 1, m + 1) if (changed[e]) edge_weight[e] = w[e];                                                                                                                                                                           
                                                                                                                                                                                                                                                    
                  // Apply updates from l to query_id-1                                                                                                                                                                                             
                  FOR(j, l, query_id) {                                                                                                                                                                                                             
                      if (t[j] == 1) edge_weight[x[j]] = y[j];                                                                                                                                                                                      
                  }                                                                                                                                                                                                                                 
                                                                                                                                                                                                                                                    
                  // Collect edges with weight >= threshold                                                                                                                                                                                         
                  for (auto [edge, weight] : edge_weight) {                                                                                                                                                                                         
                      if (weight >= y[query_id]) {                                                                                                                                                                                                  
                          query_edges[query_id].push_back(edge);                                                                                                                                                                                    
                      }                                                                                                                                                                                                                             
                  }                                                                                                                                                                                                                                 
              }                                                                                                                                                                                                                                     
          }                                                                                                                                                                                                                                         
                                                                                                                                                                                                                                                    
          // Apply final updates for next block                                                                                                                                                                                                     
          FOR(i, l, r) if (t[i] == 1) w[x[i]] = y[i];                                                                                                                                                                                               
                                                                                                                                                                                                                                                    
          // Sort queries by descending threshold                                                                                                                                                                                                   
          sort(ask.begin(), ask.end(), [&](int a, int b) { return y[a] > y[b]; });                                                                                                                                                                  
          sort(unchanged.begin(), unchanged.end(), [&](int a, int b) { return w[a] > w[b]; });                                                                                                                                                      
                                                                                                                                                                                                                                                    
          int ptr = 0;                                                                                                                                                                                                                              
          for (int query_id : ask) {                                                                                                                                                                                                                
              // Incrementally add unchanged edges >= threshold                                                                                                                                                                                     
              while (ptr < unchanged.size() && w[unchanged[ptr]] >= y[query_id]) {                                                                                                                                                                  
                  unite(u[unchanged[ptr]], v[unchanged[ptr]]);                                                                                                                                                                                      
                  ptr++;                                                                                                                                                                                                                            
              }                                                                                                                                                                                                                                     
                                                                                                                                                                                                                                                    
              // Build component graph with changed edges for this specific query                                                                                                                                                                   
              map<pair<int,int>, bool> added;
              vector<vector<int>> comp_graph(n + 1);                                                                                                                                                                                                
                                                                                                                                                                                                                                                    
              for (int edge : query_edges[query_id]) {                                                                                                                                                                                              
                  int cu = find(u[edge]);                                                                                                                                                                                                           
                  int cv = find(v[edge]);                                                                                                                                                                                                           
                                                                                                                                                                                                                                                    
                  if (cu != cv) {                                                                                                                                                                                                                   
                      auto key = minmax(cu, cv);                                                                                                                                                                                                    
                      if (!added[key]) {                                                                                                                                                                                                            
                          comp_graph[cu].push_back(cv);                                                                                                                                                                                             
                          comp_graph[cv].push_back(cu);                                                                                                                                                                                             
                          added[key] = true;                                                                                                                                                                                                        
                      }                                                                                                                                                                                                                             
                  }                                                                                                                                                                                                                                 
              }                                                                                                                                                                                                                                     
                                                                                                                                                                                                                                                    
              // DFS from query node's component                                                                                                                                                                                                    
              int start_comp = find(x[query_id]);
              ans[query_id] = dfs_count(start_comp, comp_graph);                                                                                                                                                                                    
          }                                                                                                                                                                                                                                         
      }                                                                                                                                                                                                                                             
                                                                                                                                                                                                                                                    
      FOR(i, 1, q + 1) if (t[i] == 2) cout << ans[i] << '\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