Submission #244152

#	Time	Username	Problem	Language	Result	Execution time	Memory
244152		neihcr7j	Bridges (APIO19_bridges)	C++14	46 / 100	3080 ms	7160 KiB

bridges

#include<bits/stdc++.h>

#define block 300
#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) {};
};

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[400];

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

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

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

  tem[ntem++] = {d + 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) {
    tem[ntem++] = {d + u, d[u]};
    tem[ntem++] = {d + v, d[v]};
    d[u].first = v;
    d[v].second += d[u].second;
    d[u].second = 0;
  }
}

void undo() {
  for (int i = ntem - 1; i >= 0; --i)
    (*tem[i].first) = tem[i].second;
  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;

  for (int i = 0; i < m; ++i) {
    int u, v, c;
    cin >> u >> v >> c;
    e.push_back({edge(u, v, c)});
    id[i] = 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;

    sort(id, id + m, [](int i, int j){
      return e[i].c > e[j].c;
    });

    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());
    int index = 0;

    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 (index < e.size() && e[id[index]].c >= q[k][x].b) {
        if (!ok[id[index]])
          join(e[id[index]].u, e[id[index]].v);
        index++;
      }

      ntem = 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();
    }

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

  return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:97:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < q[k].size(); ++i)
                     ~~^~~~~~~~~~~~~
bridges.cpp:109:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < q[k].size(); ++i)
                       ~~^~~~~~~~~~~~~
bridges.cpp:113:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while (index < e.size() && e[id[index]].c >= q[k][x].b) {
              ~~~~~~^~~~~~~~~~
bridges.cpp:121:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < q[k].size(); ++i)
                       ~~^~~~~~~~~~~~~
bridges.cpp:137:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < q[k].size(); ++i)
                       ~~^~~~~~~~~~~~~
bridges.cpp:146: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: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27