Submission #244214

#	Time	Username	Problem	Language	Result	Execution time	Memory
244214		neihcr7j	Bridges (APIO19_bridges)	C++14	30 / 100	3081 ms	10576 KiB

bridges

#include<bits/stdc++.h>

#define block 200
#define maxn 100005

using namespace std;
typedef long long ll;
typedef pair < int, int > II;

int n, m;
int nq;

struct edge{
  int u, v, c;
  edge(int _u = 0, int _v = 0, int _c = 0) : u(_u), v(_v), c(_c) {};

  bool operator < (const edge op) const {
    return c > op.c;
  }
};

vector < edge > e;

struct query{
  int type, a, b;
  query(int _type, int _a, int _b) : type(_type), a(_a), b(_b) {};
};

vector < query > q[1005];

int id[maxn], ok[maxn];
II d[maxn];

int ntem;
int vis[maxn];
pair < int , II > tem[maxn];

int root(int u) {
  if (u == d[u].first)
    return u;

  if (vis[u] == 0) {
    vis[u] = 1;
    tem[ntem++] = {u, d[u]};
  }

  return d[u].first = root(d[u].first);
}

void join(int u, int v) {
  u = root(u); v = root(v);

  if (u != v) {
    if (vis[v] == 0) {
      vis[v] = 1;
      tem[ntem++] = {v, d[v]};
    }

    if (vis[u] == 0) {
      vis[u] = 1;
      tem[ntem++] = {u, d[u]};
    }

    d[u].first = v;
    d[v].second += d[u].second;
    d[u].second = 0;
  }
}

void undo(int ok) {
  for (int i = ntem - 1; i >= 0; --i) {
    if (ok)
      d[tem[i].first] = tem[i].second;
    vis[tem[i].first] = 0;
  }
  ntem = 0;
}

int k;

int main(){
  #define TASK "ABC"
 // freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
  ios_base::sync_with_stdio(0);

  cin >> n >> m;

  set < pair < edge, int > > s;

  for (int i = 0; i < m; ++i) {
    int u, v, c;
    cin >> u >> v >> c;
    e.push_back({edge(u, v, c)});
    s.insert({e.back(), i});
  }

  cin >> nq;

  for (int i = 0; i < nq; ++i) {
    int type, a, b;
    cin >> type >> a >> b;

    if (type == 1)
      a--;

    q[i / block].push_back(query(type, a, b));
  }

  for (k = 0; k <= (nq - 1) / block; ++k) {
    for (int i = 1; i <= n; ++i)
      d[i] = {i, 1};
    ntem = 0;

    vector < int > ret;
    for (int i = 0; i < q[k].size(); ++i)
      if (q[k][i].type == 2)
        ret.push_back(i);

    sort(ret.begin(), ret.end(), [](int i, int j){
      return q[k][i].b > q[k][j].b;
    });

    vector < int > ans(q[k].size());
    auto iter = s.begin();

    for (auto x : ret) {
      for (int i = 0; i < q[k].size(); ++i)
        if (q[k][i].type == 1)
          ok[q[k][i].a] = 1;

      while (iter != s.end() && (iter -> first).c >= q[k][x].b) {
        if (!ok[iter -> second])
          join((iter -> first).u, (iter -> first).v);
        iter++;
      }

      undo(0);

      for (int i = 0; i < q[k].size(); ++i)
        if (q[k][i].type == 1)
          ok[q[k][i].a] = 0;

      for (int i = 0; i < x; ++i)
        if (q[k][i].type == 1)
          ok[q[k][i].a] = 1;

      for (int i = q[k].size() - 1; i >= 0; --i)
        if (q[k][i].type == 1) {
          if ((i < x && ok[q[k][i].a] && q[k][i].b >= q[k][x].b) || (i >= x && !ok[q[k][i].a] && e[q[k][i].a].c >= q[k][x].b))
            join(e[q[k][i].a].u, e[q[k][i].a].v);
          if (i >= x && ok[q[k][i].a]) continue;
          ok[q[k][i].a] = 0;
        }

      for (int i = 0; i < q[k].size(); ++i)
        if (q[k][i].type == 1)
          ok[q[k][i].a] = 0;

      ans[x] = d[root(q[k][x].a)].second;

      undo(1);
    }

    for (int i = 0; i < q[k].size(); ++i)
      if (q[k][i].type == 2)
        cout << ans[i] << '\n';
      else {
        s.erase({e[q[k][i].a], q[k][i].a});
        e[q[k][i].a].c = q[k][i].b;
        s.insert({e[q[k][i].a], q[k][i].a});
      }
  }

  return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:115:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < q[k].size(); ++i)
                     ~~^~~~~~~~~~~~~
bridges.cpp:127:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < q[k].size(); ++i)
                       ~~^~~~~~~~~~~~~
bridges.cpp:139:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < q[k].size(); ++i)
                       ~~^~~~~~~~~~~~~
bridges.cpp:155:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < q[k].size(); ++i)
                       ~~^~~~~~~~~~~~~
bridges.cpp:164:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < q[k].size(); ++i)
                     ~~^~~~~~~~~~~~~

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