oj.uz

Submission #799724

# Submission time Handle Problem Language Result Execution time Memory
799724 2023-07-31T21:10:18 Z MilosMilutinovic Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 19268 KB 
#include "collapse.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> simulateCollapse(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p) {
  int m = (int) t.size();
  int q = (int) w.size();
  for (int i = 0; i < m; i++) {
    if (x[i] > y[i]) {
      swap(x[i], y[i]);
    }
  }
  vector<int> to(m);
  map<pair<int, int>, int> mp;
  for (int i = 0; i < m; i++) {
    if (t[i] == 0) {
      to[i] = m - 1;
      mp[make_pair(x[i], y[i])] = i;
    } else {
      to[mp[make_pair(x[i], y[i])]] = i - 1;
    }
  }
  vector<vector<int>> qs(m);
  for (int i = 0; i < q; i++) {
    qs[w[i]].push_back(i);
  }
  vector<int> par(n);
  vector<int> sz(n, 1);
  vector<tuple<int, int, int>> stk;
  int comps = 0;
  iota(par.begin(), par.end(), 0);
  function<int(int)> root = [&](int x) {
    if (par[x] == x) {
      return x;
    }
    return root(par[x]);
  };
  auto Unite = [&](int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) {
      stk.emplace_back(-1, -1, -1);
      return;
    }
    if (sz[x] < sz[y]) {
      swap(x, y);
    }
    stk.emplace_back(x, y, sz[y]);
    par[y] = x;
    sz[x] += sz[y];
    comps += 1;
  };
  auto Rollback = [&](int T) {
    while ((int) stk.size() > T) {
      auto it = stk.back();
      stk.pop_back();
      int x = get<0>(it);
      int y = get<1>(it);
      int s = get<2>(it);
      if (x == -1) {
        continue;
      }
      par[y] = y;
      sz[y] = s;
      sz[x] -= s;
      comps -= 1;
    }
  };
  const int BLOCK = 6;
  vector<int> ans(q);
  for (int l = 0; l < m; l += BLOCK) {
    int r = min(m - 1, l + BLOCK - 1);
    vector<int> full;
    vector<int> half;
    for (int i = 0; i <= r; i++) {
      if (t[i] == 1 || to[i] < l) {
        continue;
      }
      if (i <= l && to[i] >= r) {
        full.push_back(i);
      } else {
        half.push_back(i);
      }
    }
    vector<int> qq;
    for (int i = l; i <= r; i++) {
      for (int j : qs[i]) {
        qq.push_back(j);
      }
    }
    {
      sort(qq.begin(), qq.end(), [&](int i, int j) {
        return p[i] < p[j];
      });
      sort(full.begin(), full.end(), [&](int i, int j) {
        return y[i] < y[j];
      });
      int ptr = 0;
      for (int i : qq) {
        while (ptr < (int) full.size() && y[full[ptr]] <= p[i]) {
          Unite(x[full[ptr]], y[full[ptr]]);
          ptr += 1;
        }
        int T = (int) stk.size();
        for (int j : half) {
          if (j <= w[i] && to[j] >= w[i] && y[j] <= p[i]) {
            Unite(x[j], y[j]);
          }
        }
        ans[i] += (p[i] + 1) - comps;
        Rollback(T);
      }
      Rollback(0);
    }
    {
      sort(qq.begin(), qq.end(), [&](int i, int j) {
        return p[i] > p[j];
      });
      sort(full.begin(), full.end(), [&](int i, int j) {
        return x[i] > x[j];
      });
      int ptr = 0;
      for (int i : qq) {
        while (ptr < (int) full.size() && x[full[ptr]] > p[i]) {
          Unite(x[full[ptr]], y[full[ptr]]);
          ptr += 1;
        }
        int T = (int) stk.size();
        for (int j : half) {
          if (j <= w[i] && to[j] >= w[i] && x[j] > p[i]) {
            Unite(x[j], y[j]);
          }
        }
        ans[i] += (n - p[i] - 1) - comps;
        Rollback(T);
      }
      Rollback(0);
    }
  }
  return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 852 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 12 ms 724 KB Output is correct
6 Correct 217 ms 1232 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 12 ms 980 KB Output is correct
10 Correct 53 ms 1088 KB Output is correct
11 Correct 311 ms 1372 KB Output is correct
12 Correct 251 ms 1360 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3760 KB Output is correct
2 Correct 23 ms 3536 KB Output is correct
3 Correct 5246 ms 11848 KB Output is correct
4 Correct 25 ms 3540 KB Output is correct
5 Correct 5317 ms 12436 KB Output is correct
6 Correct 209 ms 4436 KB Output is correct
7 Execution timed out 15065 ms 19268 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3752 KB Output is correct
2 Correct 28 ms 3792 KB Output is correct
3 Correct 29 ms 3580 KB Output is correct
4 Correct 29 ms 3504 KB Output is correct
5 Correct 36 ms 3540 KB Output is correct
6 Correct 269 ms 4680 KB Output is correct
7 Execution timed out 15073 ms 15292 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 852 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 12 ms 724 KB Output is correct
6 Correct 217 ms 1232 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 12 ms 980 KB Output is correct
10 Correct 53 ms 1088 KB Output is correct
11 Correct 311 ms 1372 KB Output is correct
12 Correct 251 ms 1360 KB Output is correct
13 Correct 24 ms 3760 KB Output is correct
14 Correct 23 ms 3536 KB Output is correct
15 Correct 5246 ms 11848 KB Output is correct
16 Correct 25 ms 3540 KB Output is correct
17 Correct 5317 ms 12436 KB Output is correct
18 Correct 209 ms 4436 KB Output is correct
19 Execution timed out 15065 ms 19268 KB Time limit exceeded
20 Halted 0 ms 0 KB -