oj.uz

Submission #244166

# Submission time Handle Problem Language Result Execution time Memory
244166 2020-07-02T17:15:58 Z neihcr7j Bridges (APIO19_bridges) C++14
30 / 100
 3000 ms 11304 KB 
#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) {};

  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;
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;

  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++;
      }

      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 {
        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

bridges.cpp: In function 'int main()':
bridges.cpp:99:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < q[k].size(); ++i)
                     ~~^~~~~~~~~~~~~
bridges.cpp:111:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < q[k].size(); ++i)
                       ~~^~~~~~~~~~~~~
bridges.cpp:123: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:148:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < q[k].size(); ++i)
                     ~~^~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 47 ms 768 KB Output is correct
4 Correct 20 ms 640 KB Output is correct
5 Correct 42 ms 640 KB Output is correct
6 Correct 40 ms 640 KB Output is correct
7 Correct 44 ms 640 KB Output is correct
8 Correct 42 ms 640 KB Output is correct
9 Correct 50 ms 640 KB Output is correct
10 Correct 41 ms 640 KB Output is correct
11 Correct 42 ms 640 KB Output is correct
12 Correct 43 ms 640 KB Output is correct
13 Correct 47 ms 640 KB Output is correct
14 Correct 46 ms 760 KB Output is correct
15 Correct 46 ms 640 KB Output is correct
16 Correct 45 ms 640 KB Output is correct
17 Correct 45 ms 640 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1597 ms 7384 KB Output is correct
2 Correct 1727 ms 7448 KB Output is correct
3 Correct 1574 ms 7276 KB Output is correct
4 Correct 1690 ms 7216 KB Output is correct
5 Correct 1683 ms 7344 KB Output is correct
6 Correct 2264 ms 9772 KB Output is correct
7 Correct 2190 ms 9464 KB Output is correct
8 Correct 2178 ms 9648 KB Output is correct
9 Correct 172 ms 2556 KB Output is correct
10 Execution timed out 3079 ms 8276 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1588 ms 5772 KB Output is correct
2 Correct 1303 ms 3452 KB Output is correct
3 Correct 2518 ms 6292 KB Output is correct
4 Correct 1907 ms 5932 KB Output is correct
5 Correct 178 ms 2552 KB Output is correct
6 Correct 2230 ms 6372 KB Output is correct
7 Correct 1908 ms 6012 KB Output is correct
8 Correct 1750 ms 6200 KB Output is correct
9 Correct 1719 ms 6380 KB Output is correct
10 Correct 1555 ms 6196 KB Output is correct
11 Correct 1552 ms 6576 KB Output is correct
12 Correct 1365 ms 6836 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3071 ms 11304 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1597 ms 7384 KB Output is correct
2 Correct 1727 ms 7448 KB Output is correct
3 Correct 1574 ms 7276 KB Output is correct
4 Correct 1690 ms 7216 KB Output is correct
5 Correct 1683 ms 7344 KB Output is correct
6 Correct 2264 ms 9772 KB Output is correct
7 Correct 2190 ms 9464 KB Output is correct
8 Correct 2178 ms 9648 KB Output is correct
9 Correct 172 ms 2556 KB Output is correct
10 Execution timed out 3079 ms 8276 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 47 ms 768 KB Output is correct
4 Correct 20 ms 640 KB Output is correct
5 Correct 42 ms 640 KB Output is correct
6 Correct 40 ms 640 KB Output is correct
7 Correct 44 ms 640 KB Output is correct
8 Correct 42 ms 640 KB Output is correct
9 Correct 50 ms 640 KB Output is correct
10 Correct 41 ms 640 KB Output is correct
11 Correct 42 ms 640 KB Output is correct
12 Correct 43 ms 640 KB Output is correct
13 Correct 47 ms 640 KB Output is correct
14 Correct 46 ms 760 KB Output is correct
15 Correct 46 ms 640 KB Output is correct
16 Correct 45 ms 640 KB Output is correct
17 Correct 45 ms 640 KB Output is correct
18 Correct 1597 ms 7384 KB Output is correct
19 Correct 1727 ms 7448 KB Output is correct
20 Correct 1574 ms 7276 KB Output is correct
21 Correct 1690 ms 7216 KB Output is correct
22 Correct 1683 ms 7344 KB Output is correct
23 Correct 2264 ms 9772 KB Output is correct
24 Correct 2190 ms 9464 KB Output is correct
25 Correct 2178 ms 9648 KB Output is correct
26 Correct 172 ms 2556 KB Output is correct
27 Execution timed out 3079 ms 8276 KB Time limit exceeded
28 Halted 0 ms 0 KB -