Submission #197642

#	Time	Username	Problem	Language	Result	Execution time	Memory
197642		quocnguyen1012	Bridges (APIO19_bridges)	C++14	0 / 100	1761 ms	524292 KiB

bridges

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 1e4 + 5, maxm = 1e5 + 5;
const int magic = 800;

struct State
{
  int Time;
  int *fi; int se;
  State(int _Time, int* _fi, int _se):
    Time(_Time), fi(_fi), se(_se) {};
};

struct pdsu
{
  vector<int> par, sz;
  vector<State> saved;
  void init(int n)
  {
    par.assign(n + 5, 0); sz.assign(n + 5, 1);
    for (int i = 0; i < n + 5; ++i){
      par[i] = i;
    }
  }
  int finds(int u, int Time)
  {
    if (par[u] != u){
      saved.pb({Time, &par[u], par[u]});
      par[u] = finds(par[u], Time);
    }
    return par[u];
  }
  bool same(int u, int v, int Time)
  {
    return finds(u, Time) == finds(v, Time);
  }
  bool merges(int u, int v, int Time)
  {
    u = finds(u, Time); v = finds(v, Time);
    if (u == v) return false;
    if (sz[u] < sz[v]) swap(u, v);
    saved.pb({Time, &par[v], par[v]});
    saved.pb({Time, &sz[u], sz[u]});
    saved.pb({Time, &sz[v], sz[v]});
    sz[u] += sz[v]; sz[v] = 0;
    par[v] = u;
    return true;
  }
  void rollback(int Time)
  {
    while (saved.back().Time == Time){
      *saved.back().fi = saved.back().se;
      saved.pop_back();
    }
  }
}dsu;

struct edge_list
{
  int u, v, w, id;
  edge_list(int u = 0, int v = 0, int w = 0, int id = 0):
    u(u), v(v), w(w), id(id) {}
  bool operator < (const edge_list & other) const
  {
    return w < other.w;
  }
};

struct Query
{
  int pos, id, val;
  bool operator < (const Query & other) const
  {
    return val < other.val;
  }
};

edge_list edge[maxm];
int N, M, Q;
int type[maxm], pos[maxm], val[maxm];
int ret[maxm], id[maxm];
bool in_quer[maxm];

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> M;
  for (int i = 1; i <= M; ++i){
    cin >> edge[i].u >> edge[i].v >> edge[i].w;
    edge[i].w = -edge[i].w;
    edge[i].id = i;
  }
  sort(edge + 1, edge + 1 + M);
  cin >> Q;
  for (int i = 1; i <= Q; ++i){
    cin >> type[i] >> pos[i] >> val[i];
    val[i] = -val[i];
  }
  for (int i = 1; i <= Q; i += magic){
    vector<int> in_tree;
    for (int j = 1; j <= M; ++j){
      id[edge[j].id] = j;
    }
    dsu.init(N);
    int Time = 0;
    for (int j = i; j <= Q && j < i + magic; ++j){
      if (type[j] == 1){
        in_quer[id[pos[j]]] = true;
      }
    }
    for (int j = 1; j <= M; ++j){
      if (in_quer[j] == false){
        if (dsu.merges(edge[j].u, edge[j].v, 0)){
          in_tree.pb(j);
        }
      }
    }
    dsu.init(N);
    vector<Query> qr;
    vector<int> logs;
    for (int j = i; j <= Q && j < i + magic; ++j){
      if (type[j] == 1){
        if (in_quer[id[pos[j]]]){
          logs.pb(pos[j]);
          in_quer[id[pos[j]]] = false;
        }
      }
      else{
        qr.pb({pos[j], j, val[j]});
      }
    }
    sort(qr.begin(), qr.end());
    vector<int> change(M + 5);
    int pt = 0;
    for (auto & all : qr){
      while (pt < (int)in_tree.size() && edge[in_tree[pt]].w <= all.val){
        dsu.merges(edge[in_tree[pt]].u, edge[in_tree[pt]].v, 0);
        ++pt;
      }
      for (int j = i; j < all.id; ++j){
        if (type[j] == 1){
          change[pos[j]] = val[j];
        }
      }
      for (auto & it : logs){
        int cost;
        if (change[it] == 0) cost = edge[id[it]].w;
        else cost = change[it];
        if (cost <= all.val) dsu.merges(edge[id[it]].u, edge[id[it]].v, 1);
      }
      ret[all.id] = dsu.sz[dsu.finds(all.pos, 1)];
      dsu.rollback(1);
      for (int j = i; j < all.id; ++j){
        if (type[j] == 1){
          change[pos[j]] = 0;
        }
      }
    }
    for (int j = i; j <= Q && j < i + magic; ++j){
      change[pos[j]] = val[j];
    }
    vector<edge_list> l, r;
    for (int j = 1; j <= M; ++j){
      if (change[edge[j].id]){
        edge[j].w = change[edge[j].id];
        change[edge[j].id] = 0;
        r.pb(edge[j]);
      }
      else l.pb(edge[j]);
    }
    sort(r.begin(), r.end());
    merge(l.begin(), l.end(), r.begin(), r.end(), edge + 1);
  }
  for (int i = 1; i <= Q; ++i){
    if (type[i] == 2) cout << ret[i] << '\n';
  }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:117:9: warning: unused variable 'Time' [-Wunused-variable]
     int Time = 0;
         ^~~~
bridges.cpp:96:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
bridges.cpp:97:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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