Submission #1356096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1356096		srividya_06	다리 (APIO19_bridges)	C++20	0 / 100	3094 ms	6516 KiB

bridges

 #include <bits/stdc++.h>                                                                                                                                                                                                                          
  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_on_components(int start, vector<vector<int>>& graph, int* sizes) {                                                                                                                                                                        
      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 += sizes[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 (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] >> 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, upd;                                                                                                                                                                                                                     
          for (int i = l; i < r; i++) {                                                                                                                                                                                                             
              if (t[i] == 1) {                                                                                                                                                                                                                      
                  changed[x[i]] = true;                                                                                                                                                                                                             
                  upd.push_back(i);                                                                                                                                                                                                                 
              } else {                                                                                                                                                                                                                              
                  ask.push_back(i);                                                                                                                                                                                                                 
              }                                                                                                                                                                                                                                     
          }                                                                                                                                                                                                                                         
                                                                                                                                                                                                                                                    
          // Apply updates                                                                                                                                                                                                                          
          for (int i : upd) w[x[i]] = y[i];                                                                                                                                                                                                         
                                                                                                                                                                                                                                                    
          // Collect unchanged edges                                                                                                                                                                                                                
          vector<pair<int,int>> unchanged;                                                                                                                                                                                                          
          for (int i = 1; i <= m; i++) {                                                                                                                                                                                                            
              if (!changed[i]) {                                                                                                                                                                                                                    
                  unchanged.push_back({w[i], i});                                                                                                                                                                                                   
              }                                                                                                                                                                                                                                     
          }                                                                                                                                                                                                                                         
          sort(unchanged.rbegin(), unchanged.rend());                                                                                                                                                                                               
                                                                                                                                                                                                                                                    
          // Sort queries by threshold descending                                                                                                                                                                                                   
          sort(ask.begin(), ask.end(),                                                                                                                                                                                                              
               [&](int a, int b) { return y[a] > y[b]; });                                                                                                                                                                                          
                                                                                                                                                                                                                                                    
          int ptr = 0;                                                                                                                                                                                                                              
          for (int query_id : ask) {                                                                                                                                                                                                                
              // Add unchanged edges >= threshold                                                                                                                                                                                                   
              while (ptr < unchanged.size() && unchanged[ptr].first >= y[query_id]) {                                                                                                                                                               
                  int edge = unchanged[ptr].second;                                                                                                                                                                                                 
                  unite(u[edge], v[edge]);                                                                                                                                                                                                          
                  ptr++;                                                                                                                                                                                                                            
              }                                                                                                                                                                                                                                     
                                                                                                                                                                                                                                                    
              // Build component graph with changed edges                                                                                                                                                                                           
              map<pair<int,int>, bool> added;                                                                                                                                                                                                       
              vector<vector<int>> comp_graph(n + 1);                                                                                                                                                                                                
                                                                                                                                                                                                                                                    
              for (int update_id : upd) {                                                                                                                                                                                                           
                  if (w[x[update_id]] >= y[query_id]) {                                                                                                                                                                                             
                      int edge = x[update_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_on_components(start_comp, comp_graph, sz);                                                                                                                                                                        
          }                                                                                                                                                                                                                                         
      }
                                                                                                                                                                                                                                                    
      for (int i = 1; i <= q; i++) {                                                                                                                                                                                                                
          if (t[i] == 2) cout << ans[i] << '\n';                                                                                                                                                                                                    
      }                                                                                                                                                                                                                                             
  }               
                                                 

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