Submission #120810

#	Time	Username	Problem	Language	Result	Execution time	Memory
120810		nvmdava	Bridges (APIO19_bridges)	C++17	100 / 100	2506 ms	10048 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define SIZE 400
#define N 50005
#define M 100005

int ans[M], n, m;
struct Path{
   int w, id, v, u;
   bool act = 0;
   Path(int _v, int _u, int _w, int _id){
      w = _w; v = _v; u = _u; id = _id;
   }
   bool operator<(const Path& rhs) const {
      return w > rhs.w;
   }
};

struct Query{
   int w, id, v;
   Query(int _v, int _w, int _id){
      w = _w; id = _id, v = _v;
   }
   bool operator<(const Query& rhs) const {
      return w > rhs.w;
   }
};

struct Update{
   int id, w, v;
   Update(int _v, int _w, int _id){
      id = _id; v = _v; w = _w;
   }
};

vector<Path> lists;
vector<Update> upd;
vector<Query> que;
int newOrd[M];
vector<int> adj[N];
int p[N], sz[N];

int find(int v){
   if(v == p[v]) return v;
   return p[v] = find(p[v]);
}

void merge(int v, int u){
   v = find(v);
   u = find(u);
   if(v == u) return;
   if(sz[v] > sz[u]) swap(v, u);
   p[v] = u;
   sz[u] += sz[v];
}

bool in[N];

void dfs(int v, int id){
   in[v] = 1;
   ans[id] += sz[v];
   for(int x : adj[v]){
      if(in[x]) continue;
      dfs(x, id);
   }
}

void process(){
   sort(lists.begin(), lists.end());
   for(int i = 0; i < m; i++)
      newOrd[lists[i].id] = i;
   for(int i = 1; i <= n; i++){
      p[i] = i;
      sz[i] = 1;
   }

   reverse(upd.begin(), upd.end());
   for(int i = upd.size() - 1; i >= 0; i--){
      if(lists[newOrd[upd[i].v]].act == 0){
         upd.push_back(Update(upd[i].v, lists[newOrd[upd[i].v]].w, 0));
         lists[newOrd[upd[i].v]].act = 1;
      }
   }

   sort(que.begin(), que.end());
   int now = 0;
   for(auto& q : que){
      while(now != m && lists[now].w >= q.w){
         if(lists[now].act == 0) merge(lists[now].v, lists[now].u);
         now++;
      }
      vector<int> pos;
      int i;
      for(i = 0; i < upd.size(); i++){
         if(upd[i].id > q.id) continue;
         if(lists[newOrd[upd[i].v]].act == 0) continue;
         lists[newOrd[upd[i].v]].act = 0;
         if(upd[i].w < q.w) continue;
         int v = lists[newOrd[upd[i].v]].v, u = lists[newOrd[upd[i].v]].u;
         v = find(v);
         u = find(u);
         if(v == u) continue;
         adj[v].push_back(u);
         adj[u].push_back(v);
         pos.push_back(u);
         pos.push_back(v);
      }
      dfs(find(q.v), q.id);
      for(int x : pos){
         adj[x].clear();
         in[x] = 0;
      }
      in[find(q.v)] = 0;
      for(i = i - 1; i >= 0; i--){
         lists[newOrd[upd[i].v]].act = 1;
      }
   }

   //End
   for(int i = upd.size() - 1; i >= 0; i--){
      lists[newOrd[upd[i].v]].act = 0;
      lists[newOrd[upd[i].v]].w = upd[i].w;
   }
   que.clear();
   upd.clear();
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

   cin>>n>>m;

   for(int i = 1; i <= m; i++){
      int v, u, d;
      cin>>v>>u>>d;
      lists.push_back(Path(v, u, d, i));
   }
   int q;
   cin>>q;
   for(int j = 1; j <= q; j++){
      int t, v, w;
      cin>>t>>v>>w;
      if(t == 2){
         que.push_back(Query(v, w, j));
      } else {
         upd.push_back(Update(v, w, j));
      }
      if(j % SIZE == 0){
         process();
      }
   }
   process();
   for(int i = 1; i < M; i++){
      if(ans[i]) cout<<ans[i]<<'\n';
   }
}

Compilation message (stderr)

bridges.cpp: In function 'void process()':
bridges.cpp:94:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(i = 0; i < upd.size(); i++){
                  ~~^~~~~~~~~~~~

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