Submission #823554

#	Time	Username	Problem	Language	Result	Execution time	Memory
823554		mgl_diamond	Bridges (APIO19_bridges)	C++17	73 / 100	3073 ms	10340 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
 
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define file "input"
 
void setIO(string name="") {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen(file".in", "r")) {
    freopen(file".in", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}

const int N = 5e4+5;
int SQRT;

struct Edge {
  int u, v, w, i;
  bool changed = 0, fixed = 0;
  Edge(int _u=0, int _v=0, int _w=0, int _i=0) : u(_u), v(_v), w(_w), i(_i) {}
  bool operator < (const Edge &b) const {
    return w < b.w;
  }
};

int n, m, q;

// dsu
int par[N], siz[N];
stack<int> app;
vector<pair<ii, int>> block;

// graph
vector<Edge> e;
vector<int> adj[N];
int id[N*2];

int root(int u) {
  while (par[u] != u) u = par[u];
  return u;
}

void join(int u, int v, bool save) {
  if ((u = root(u)) == (v = root(v))) return;
  if (siz[u] < siz[v]) swap(u, v);
  if (save) app.push(v);
  siz[u] += siz[v];
  par[v] = u;
}

void roll_back() {
  while (!app.empty()) {
    auto v = app.top();
    app.pop();
    siz[par[v]] -= siz[v];
    par[v] = v;
  }
}

void solve() {
  vector<pair<ii, int>> querys;
  vector<int> ans(sz(block));
  foru(i, 0, sz(block)-1) if (block[i].se == 2) 
    querys.push_back({block[i].fi, i});
  
  sort(all(querys), [&](pair<ii, int> a, pair<ii, int> b){
    return a.fi.se > b.fi.se;
  });

  foru(i, 1, n) {
    par[i] = i;
    siz[i] = 1;
  }

  int j = m-1;
  foru(i, 0, sz(querys)-1) {
    int node = querys[i].fi.fi, val = querys[i].fi.se;
    while (j >= 0) {
      if (e[j].w < val) break;
      if (!e[j].changed) join(e[j].u, e[j].v, 0);
      --j;
    }

    int pos = querys[i].se;
    ford(k, pos-1, 0) if (block[k].se == 1) {
      int idEdge = id[block[k].fi.fi-1], to = block[k].fi.se;
      if (e[idEdge].fixed) continue;
      e[idEdge].fixed = true;
      if (to >= val) join(e[idEdge].u, e[idEdge].v, 1);
    }
    foru(k, pos+1, sz(block)-1) if (block[k].se == 1) {
      int idEdge = id[block[k].fi.fi-1];
      if (e[idEdge].fixed) continue;
      if (e[idEdge].w >= val) join(e[idEdge].u, e[idEdge].v, 1);
    }
    ford(k, pos-1, 0) if (block[k].se == 1) {
      int idEdge = id[block[k].fi.fi-1];
      e[idEdge].fixed = 0;
    }
    ans[pos] = siz[root(node)];
    roll_back();
  }

  foru(i, 0, sz(block)-1) {
    if (block[i].se == 2)
      cout << ans[i] << "\n";
    else {
      int idEdge = id[block[i].fi.fi-1];
      e[idEdge].changed = e[idEdge].fixed = 0;
      e[idEdge].w = block[i].fi.se;
    }
  }
  sort(all(e));
  foru(i, 0, m-1) id[e[i].i] = i;
  block.clear();
}

int main() {
  setIO();

  cin >> n >> m;
  SQRT = sqrt(n);

  foru(i, 0, m-1) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back(i);
    adj[v].push_back(i);
    e.emplace_back(u, v, w, i);
  }

  sort(all(e));
  foru(i, 0, m-1) id[e[i].i] = i;

  cin >> q;
  foru(r, 1, q) {
    int t, x, y;
    cin >> t >> x >> y;
    if (t == 1) e[id[x-1]].changed = true;
    block.push_back({{x, y}, t});
    if (r == q || sz(block) == SQRT) solve();
  }
}

Compilation message (stderr)

bridges.cpp: In function 'void setIO(std::string)':
bridges.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen(file".in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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