oj.uz

답안 #244151

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
244151 2020-07-02T16:49:18 Z neihcr7j 다리 (APIO19_bridges) C++14
16 / 100
 3000 ms 6720 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) {};
};

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 && ((i < x && q[k][i].b >= q[k][x].b && ok[q[k][i].a]) || (i >= x && e[q[k][i].a].c >= q[k][x].b && !ok[q[k][i].a]))) {
          ok[q[k][i].a] = 0;
          join(e[q[k][i].a].u, e[q[k][i].a].v);
        }

      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

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

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Incorrect 41 ms 640 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2227 ms 4424 KB Output is correct
2 Correct 2120 ms 4080 KB Output is correct
3 Correct 2175 ms 4168 KB Output is correct
4 Correct 2300 ms 4340 KB Output is correct
5 Correct 2314 ms 4180 KB Output is correct
6 Correct 2734 ms 6520 KB Output is correct
7 Correct 2805 ms 6528 KB Output is correct
8 Correct 2697 ms 6628 KB Output is correct
9 Correct 191 ms 2680 KB Output is correct
10 Correct 1656 ms 5360 KB Output is correct
11 Correct 1527 ms 4976 KB Output is correct
12 Correct 2110 ms 6720 KB Output is correct
13 Correct 2005 ms 6128 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1912 ms 3812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3074 ms 5484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2227 ms 4424 KB Output is correct
2 Correct 2120 ms 4080 KB Output is correct
3 Correct 2175 ms 4168 KB Output is correct
4 Correct 2300 ms 4340 KB Output is correct
5 Correct 2314 ms 4180 KB Output is correct
6 Correct 2734 ms 6520 KB Output is correct
7 Correct 2805 ms 6528 KB Output is correct
8 Correct 2697 ms 6628 KB Output is correct
9 Correct 191 ms 2680 KB Output is correct
10 Correct 1656 ms 5360 KB Output is correct
11 Correct 1527 ms 4976 KB Output is correct
12 Correct 2110 ms 6720 KB Output is correct
13 Correct 2005 ms 6128 KB Output is correct
14 Incorrect 1912 ms 3812 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Incorrect 41 ms 640 KB Output isn't correct
4 Halted 0 ms 0 KB -