Submission #244139

#TimeUsernameProblemLanguageResultExecution timeMemory
244139neihcr7j다리 (APIO19_bridges)C++17
16 / 100
3068 ms9364 KiB
#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};

    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 < q[k].size(); ++i)
        if (q[k][i].type == 1 && ((i < x && q[k][i].b >= q[k][x].b) || (i >= x && e[q[k][i].a].c >= q[k][x].b)))
          join(e[q[k][i].a].u, e[q[k][i].a].v);

      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:96:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < q[k].size(); ++i)
                     ~~^~~~~~~~~~~~~
bridges.cpp:108:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < q[k].size(); ++i)
                       ~~^~~~~~~~~~~~~
bridges.cpp:112: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:120:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < q[k].size(); ++i)
                       ~~^~~~~~~~~~~~~
bridges.cpp:124:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < q[k].size(); ++i)
                       ~~^~~~~~~~~~~~~
bridges.cpp:133:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < q[k].size(); ++i)
                     ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...