Submission #278077

#	Time	Username	Problem	Language	Result	Execution time	Memory
278077		arman_ferdous	Bridges (APIO19_bridges)	C++17	59 / 100	3084 ms	11076 KiB

bridges

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

#define pb push_back
#define all(v) v.begin(),v.end()

using ll = long long;
using ii = pair<ll,ll>;

const int N = 5e4+10;
const int M = 1e5+10;
const int K = 500;

int n, m, qq, ans[M];
struct edge {
  int u, v, w, id;
}e[M];

struct setcomp{
  bool operator()(const edge &a, const edge &b) const {
    if(a.w != b.w) return a.w > b.w;
    return a.id < b.id;    
  }
};

multiset<edge, setcomp> ds;

struct query {
  int ty;
  int x, y;
  int id;
  // ty == 1 : bridge id, new weight
  // ty == 2 : source, car weight
}q[M];

bool edgeType[M];
vector<int> qid;

int p[N], compsz[N];

int taken[M];

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

void join(int u, int v) {
  u = find(u), v = find(v);
  if(u == v) return;
  p[u] = v;
  compsz[v] += compsz[u];
}

int vis[N], cnt;
vector<int> blockupd;
int vislist[N], vlptr;
int edgelist[M + M], elptr;

struct graph{
  int u, v, w, prev;
}E[M + M];
int node, last[N];

void addedge(int u, int v, int w) {
  E[++node] = {u, v, w, last[u]};
  last[u] = node;
  E[++node] = {v, u, w, last[v]};
  last[v] = node;
}

void dfs(int u, int w) {
  cnt += compsz[u];
  vis[u] = 1;
  vislist[vlptr++] = u;
  for(int id = last[u]; id; id = E[id].prev) {
    if(!vis[E[id].v] && w <= E[id].w) dfs(E[id].v, w);
  }
}

int main() {
  scanf("%d %d", &n, &m);
  for(int i = 0; i < m; ++i) {
    scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);
    ds.insert({e[i].u, e[i].v, e[i].w, i});
  }
  scanf("%d", &qq); int qp = 0;
  for(int i = 0; i < qq; ++i) {
    scanf("%d %d %d", &q[i].ty, &q[i].x, &q[i].y);
    if(q[i].ty == 2) q[i].id = qp++;
    else q[i].x--;
  }

  for(int l = 0; l < qq; l += K) {
    qid.clear(); blockupd.clear();
    int r = min(l + K, qq);

    // find out which edges will get changed in this block
    for(int i = 0; i < m; ++i) edgeType[i] = true;
    for(int i = l; i < r; ++i) {
      if(q[i].ty == 1) {
        edgeType[q[i].x] = false;
        blockupd.pb(i);
      }
      else qid.pb(i);
    }
    reverse(all(blockupd));
    // solve queries in descending order of weight, so that we can maintain a dsu
    sort(all(qid), [](int i, int j) {
      return q[i].y > q[j].y;
    });
    for(int i = 1; i <= n; ++i) p[i] = i, compsz[i] = 1;

    auto it = ds.begin();
    for(int id : qid) {
      // Add edges with capacity >= (this query weight) which will not be updated in this block
      while(it != ds.end()) {
        while(it != ds.end() && edgeType[it->id] == false) it++;
        if(it != ds.end() && it->w >= q[id].y) {
          join(it->u, it->v);
          it++;
        } else break;
      }

      // Add edges that got updated in this block just before this query
      for(int i = id - 1; i >= l; --i) {
        if(q[i].ty == 1 && !taken[q[i].x]) {
          addedge(find(e[q[i].x].u), find(e[q[i].x].v), q[i].y);
          taken[q[i].x] = 1;
          edgelist[elptr++] = q[i].x;
        }
      }

      // Add edges that get updated in this block but not before this query
      for(int i : blockupd) if(!taken[q[i].x]) {
        addedge(find(e[q[i].x].u), find(e[q[i].x].v), e[q[i].x].w);
        taken[q[i].x] = 1;
        edgelist[elptr++] = q[i].x;
      }

      cnt = 0;
      dfs(find(q[id].x), q[id].y);
      ans[q[id].id] = cnt;

      // Clear stuffs
      node = 0;
      for(int i = 0; i < vlptr; ++i) vis[vislist[i]] = 0;
      for(int i = 0; i < elptr; ++i) {
        last[find(e[edgelist[i]].u)] = 0;
        last[find(e[edgelist[i]].v)] = 0;
        taken[edgelist[i]] = 0;
      }
      vlptr = elptr = 0;
    }
    // Update edges in e[] that got updated
    reverse(all(blockupd));
    for(int i : blockupd) {
      auto it = ds.find({e[q[i].x].u, e[q[i].x].v, e[q[i].x].w, q[i].x});
      ds.erase(it);
      e[q[i].x].w = q[i].y;
      ds.insert({e[q[i].x].u, e[q[i].x].v, e[q[i].x].w, q[i].x});
    }
  }
  for(int i = 0; i < qp; ++i) 
    printf("%d\n", ans[i]);
  return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |     scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |   scanf("%d", &qq); int qp = 0;
      |   ~~~~~^~~~~~~~~~~
bridges.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |     scanf("%d %d %d", &q[i].ty, &q[i].x, &q[i].y);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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