Submission #335830

#	Time	Username	Problem	Language	Result	Execution time	Memory
335830		LifeHappen__	Bridges (APIO19_bridges)	C++14	59 / 100	3011 ms	11928 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

#define ii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

const int N = 1e5 + 5;
int n, m, q;
vector<int> adj[N];
int cha[N], tw[N];
int ans[N], wi[N], dd[N];

struct rolltime {
  int u, w, time;
  rolltime() {};
  rolltime(int _u = 0, int _w = 0, int _time = 0) :
    u(_u), w(_w), time(_time) {};
};
struct dsu {
  vector<int> id;
  vector<rolltime> rollback;
  dsu () {};
  void init(int n) {
    id.resize(n + 5, 0);
    fill(begin(id), end(id), -1);
    rollback.clear();
    assert(rollback.empty());
  }
  int findset(int u) {
    if(id[u] < 0) return u;
    return id[u] = findset(id[u]);
  }
  void mergeset(int u, int v) {
    u = findset(u);
    v = findset(v);
    if(u == v) return;
    if(id[u] > id[v]) swap(u, v);
    id[u] += id[v];
    id[v] = u;
  }
  int sz(int u) {
    return -id[u];
  }
} tpa;
struct edge {
  int u, v, w;
  edge (int _u = 0, int _v = 0, int _w = 0) :
    u(_u), v(_v), w(_w) {};
  bool operator < (edge tr) {
    return w < tr.w;
  }
} a[N];
struct Query {
  int type, u, v;
  Query (int _type = 0, int _u = 0, int _v = 0) :
    type(_type), u(_u), v(_v) {};
  bool operator < (Query a) {
    return v < a.v;
  }
} qry[N];
void link(int u, int v) {
  //cerr << u << ' ' << v;
  u = tpa.findset(u);
  v = tpa.findset(v);
  assert(u && v);
  adj[u].pb(v); adj[v].pb(u);
}
void read_inputs() {
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    a[i] = edge(u, v, w);
    wi[i] = w;
  }
  tpa.init(n);
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    int type, u, v;
    cin >> type >> u >> v;
    qry[i] = Query(type, u, v);
  }
}
void solve() {
  int SQ = 455;
  vector<ii> ord;
  vector<array<int, 3>> qt[3];
  for (int i = 1; i <= q; ++i) {
    int type = qry[i].type, u = qry[i].u, v = qry[i].v;
    if(type == 1) {
      cha[u] = 1;
    }
    qt[type].push_back({v, u, i});
    if(i % SQ == 0 || i == q) {
      tpa.init(n);
      for (int j = 1; j <= m; ++j) {
        if(!cha[j]) {
          ord.eb(wi[j], j);
        }
      }
      sort(begin(ord), end(ord));
      sort(begin(qt[2]), end(qt[2]));
      while(qt[2].size()) {
        auto t = qt[2].back(); qt[2].pop_back();
        while(ord.size() && (ord.back()).fi >= t[0]) {
          ii now = ord.back();
          int u = a[now.se].u, v = a[now.se].v;
          tpa.mergeset(u, v);
          ord.pop_back();
        }
        for (auto &v : qt[1]) {
          tw[v[1]] = wi[v[1]];
        }
        for (auto &v : qt[1]) {
          if(v[2] < t[2]) {
            tw[v[1]] = v[0];
          }
        }
        for (auto &v : qt[1]) {
          if(tw[v[1]] >= t[0]) {
            link(a[v[1]].u, a[v[1]].v);
          }
        }
        vector<int> ver;
        function<void(int)> dfs=[&](int u) {
          ver.pb(u);
          dd[u] = 1;
          //cerr << u << ' ';
          for(auto &vv : adj[u]) {
            if(!dd[vv]) dfs(vv);
          }
        };
        //cerr << '\n';
        dfs(tpa.findset(t[1]));
        //cerr << '\n';
        while(ver.size()) {
          int u = ver.back();
          ver.pop_back();
          ans[t[2]] += tpa.sz(u);
          dd[u] = 0;
        }
        for (auto &v : qt[1]) {
          int u = tpa.findset(a[v[1]].u);
          int vv = tpa.findset(a[v[1]].v);
          adj[u].clear();
          adj[vv].clear();
        }
      }
      for (int j = 1; j <= m; ++j) cha[j] = 0;
      for (auto &_ : qt[1]) wi[_[1]] = _[0];
      qt[1].clear();
      qt[2].clear();
      ord.clear();
    }
  }
  for (int i = 1; i <= q; ++i) {
    if(qry[i].type == 2) {
      cout << ans[i] << '\n';
    }
  }
}

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

  #define task "limit"
  //freopen(task".inp", "r", stdin);
  //freopen(task".out", "w", stdout);

  read_inputs();
  solve();
}

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