Submission #912665

#	Time	Username	Problem	Language	Result	Execution time	Memory
912665		duckindog	Bridges (APIO19_bridges)	C++14	100 / 100	2698 ms	33652 KiB

bridges

// from duckindog wth depression
#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10,
          S = 1e3;
int n, m;
struct edge {
  int u, v, w;
  edge() : u(0), v(0), w(0) {}
  edge(int u, int v, int w) : u(u), v(v), w(w) {}
} ed[N];
int q;
struct type {
  int ty, s, w, t;
  type() : ty(0), s(0), w(0), t(0) {}
  type(int ty, int s, int w, int t) : ty(ty), s(s), w(w), t(t) {}
} Q[N];

set<int> ad[N];
vector<int> rrh;
map<int, int> rvs;

bool mk[N];
int par[N];
int root(int u) {
  while (par[u] >= 0) u = par[u];
  return u;
}
stack<tuple<int, int, int, int>> undo;
void add(int u, int v, bool spe = 0) {
  u = root(u); v = root(v);
  if (u == v) return;
  if (par[u] > par[v]) swap(u, v);

  if (spe) undo.emplace(u, v, par[u], par[v]);
  par[u] += par[v];
  par[v] = u;

}
int ti[N];

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int u, v, w; cin >> u >> v >> w;
    ed[i] = {u, v, w};
    rrh.push_back(w);
  }
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    int ty, s, w; cin >> ty >> s >> w;
    Q[i] = {ty, s, w, i};

    if (ty == 1) rrh.push_back(w);
  }

  sort(rrh.begin(), rrh.end());
  rrh.resize(unique(rrh.begin(), rrh.end()) - rrh.begin());
  for (int i = 0; i < rrh.size(); ++i) rvs[rrh[i]] = i;

  for (int i = 1; i <= m; ++i) ad[rvs[ed[i].w]].insert(i);

  for (int i = 1; i <= q; ++i) {
    if ((i - 1) % S == 0) {
      int r = min(q, i + S - 1);
      sort(Q + i, Q + r + 1, [&](type a, type b) {
        return make_pair(a.w, -a.t) > make_pair(b.w, -b.t);
      });
    }
  }

  int it;
  vector<int> answer(q + 1);
  for (int i = 1; i <= q; ++i) {

    int l = (i - 1) / S * S + 1;
    int r = min(q, ((i - 1) / S + 1) * S);

    if ((i - 1) % S == 0) {
      if (i > 1) {
        int pl = (i - 2) / S * S + 1, pr = min(q, ((i - 2) / S + 1) * S);
        sort(Q + pl, Q + pr + 1, [&](type a, type b) {
          return a.t < b.t;
        });

        for (int j = pl; j <= pr; ++j) {
          if (Q[j].ty == 2) continue;
          int s = Q[j].s;
          ad[rvs[ed[s].w]].erase(s);
          ad[rvs[Q[j].w]].insert(s);
          ed[s].w = Q[j].w;
        }
      }

      it = rrh.size() - 1;
      memset(par, -1, sizeof par);
      stack<tuple<int, int, int, int>> k;
      swap(undo, k);
    }

    if (Q[i].ty == 1) continue;
    int s = Q[i].s, w = Q[i].w, t = Q[i].t;

    //undo
    while (undo.size()) {
      int u, v, pu, pv; tie(u, v, pu, pv) = undo.top(); undo.pop();
      par[u] = pu; par[v] = pv;
    }


    memset(mk, 0, sizeof mk);

    for (int j = l; j <= r; ++j) {
      if (Q[j].ty == 1) mk[Q[j].s] = 1;
    }

    while (it >= 0 && rrh[it] >= w) {

      for (auto j : ad[it]) {

        if (!mk[j]) add(ed[j].u, ed[j].v);

      }
      it -= 1;
    }

    memset(ti, 0, sizeof ti);
    for (int j = l; j <= r; ++j) if (Q[j].ty == 1 && Q[j].t < t) ti[Q[j].s] = max(ti[Q[j].s], Q[j].t);


    for (int j = l; j <= r; ++j) {
      int s = Q[j].s;


      if (Q[j].ty == 1 && Q[j].t > t && ed[s].w >= w && !ti[s]) {
        add(ed[s].u, ed[s].v, 1);
      }

      if (Q[j].ty == 1 && Q[j].t < t && Q[j].w >= w && ti[s] == Q[j].t) {
        add(ed[s].u, ed[s].v, 1);
      }

    }

    answer[t] = -par[root(s)];

  }

  for (int i = 1; i <= q; ++i)
    if(answer[i]) cout << answer[i] << '\n';

}

Compilation message (stderr)

bridges.cpp: In function 'int32_t main()':
bridges.cpp:67:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for (int i = 0; i < rrh.size(); ++i) rvs[rrh[i]] = i;
      |                   ~~^~~~~~~~~~~~
bridges.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:49:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:80:7: warning: 'it' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |   int it;
      |       ^~

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