oj.uz

Submission #500332

# Submission time Handle Problem Language Result Execution time Memory
500332 2021-12-30T18:40:07 Z 600Mihnea Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 6456 KB 
#include "collapse.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> brute(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]);
      assert(0 <= x[i] && x[i] < y[i] && y[i] < n);
    }
  }

  assert((int) t.size() == m);
  assert((int) x.size() == m);
  assert((int) y.size() == m);

  assert((int) w.size() == q);
  assert((int) p.size() == q);

  vector<int> sol((int) w.size());

  for (int iq = 0; iq < (int) w.size(); iq++) {
    set<pair<int, int>> s;
    for (int i = 0; i <= w[iq]; i++) {
      pair<int, int> cur = make_pair(x[i], y[i]);
      if (s.count(cur)) {
        s.erase(cur);
      } else {
        s.insert(cur);
      }
    }
    vector<pair<int, int>> ve;
    for (auto &it : s) {
      if (it.first <= p[iq] && it.second > p[iq]) {
        continue;
      }
      ve.push_back(it);
    }
    vector<int> t(n);
    iota(t.begin(), t.end(), 0);
    int comps = n;
    function<int(int)> getpap = [&] (int a) {
      if (t[a] == a) {
        return a;
      } else {
        return t[a] = getpap(t[a]);
      }
    };
    function<void(int, int)> unite = [&] (int a, int b) {
      a = getpap(a);
      b = getpap(b);
      if (a != b) {
        comps--;
        t[a] = b;
      }
    };
    for (auto &it : ve) {
      unite(it.first, it.second);
    }
    sol[iq] = comps;
  }
  return sol;
}

//const int edgeM = 333;
const int edgeM = 7;

vector<int> smart(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]);
      assert(0 <= x[i] && x[i] < y[i] && y[i] < n);
    }
  }

  assert((int) t.size() == m);
  assert((int) x.size() == m);
  assert((int) y.size() == m);

  assert((int) w.size() == q);
  assert((int) p.size() == q);

  vector<int> sol((int) w.size());


  for (int ISTEP = 1; ISTEP <= 2; ISTEP++) {
    vector<int> edgeBucket(m), edgeFirst(m), edgeLast(m);

    for (int i = 0; i < m; i++) {
      edgeBucket[i] = i / edgeM;
      edgeLast[edgeBucket[i]] = i;
    }
    for (int i = m - 1; i >= 0; i--) {
      edgeFirst[edgeBucket[i]] = i;
    }

    vector<vector<int>> inds(m);
    for (int i = 0; i < q; i++) {
      inds[w[i]].push_back(i);
    }


    set<pair<int, int>> s;
    for (int edgeBucketId = edgeBucket[0]; edgeBucketId <= edgeBucket[m - 1]; edgeBucketId++) {
      for (int step = edgeFirst[edgeBucketId]; step <= edgeLast[edgeBucketId]; step++) {
        pair<int, int> cur = make_pair(x[step], y[step]);
        if (s.count(cur)) {
          s.erase(cur);
        } else {
          s.insert(cur);
        }
        for (auto &iq : inds[step]) {
          vector<pair<int, int>> ve;
          for (auto &it : s) {
            if (it.second <= p[iq]) {
              ve.push_back(it);
              continue;
            }
          }

          vector<int> t(n);
          iota(t.begin(), t.end(), 0);
          int comps = p[iq] + 1;
          function<int(int)> getpap = [&] (int a) {
            if (t[a] == a) {
              return a;
            } else {
              return t[a] = getpap(t[a]);
            }
          };
          function<void(int, int)> unite = [&] (int a, int b) {
            a = getpap(a);
            b = getpap(b);
            if (a != b) {
              comps--;
              t[a] = b;
            }
          };
          for (auto &it : ve) {
            unite(it.first, it.second);
          }
          sol[iq] += comps;
        }
      }
    }
    for (int i = 0; i < m; i++) {
      swap(x[i], y[i]);
      x[i] = n - 1 - x[i];
      y[i] = n - 1 - y[i];
    }
    for (int i = 0; i < q; i++) {
      p[i] = n - 2 - p[i];
    }
  }
  return sol;
}

vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
	auto B=brute(N,T,X,Y,W,P);
	auto S=smart(N,T,X,Y,W,P);


	assert(B==S);
	return S;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 836 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 10 ms 460 KB Output is correct
4 Correct 20 ms 480 KB Output is correct
5 Correct 1219 ms 836 KB Output is correct
6 Correct 4006 ms 1276 KB Output is correct
7 Correct 37 ms 504 KB Output is correct
8 Correct 39 ms 464 KB Output is correct
9 Correct 1119 ms 856 KB Output is correct
10 Correct 2440 ms 1052 KB Output is correct
11 Correct 4057 ms 1392 KB Output is correct
12 Correct 4370 ms 1304 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4256 KB Output is correct
2 Correct 64 ms 4044 KB Output is correct
3 Execution timed out 15076 ms 6456 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 4292 KB Output is correct
2 Correct 83 ms 3908 KB Output is correct
3 Correct 163 ms 4044 KB Output is correct
4 Correct 332 ms 4164 KB Output is correct
5 Correct 5706 ms 4048 KB Output is correct
6 Execution timed out 15083 ms 3756 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 836 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 10 ms 460 KB Output is correct
4 Correct 20 ms 480 KB Output is correct
5 Correct 1219 ms 836 KB Output is correct
6 Correct 4006 ms 1276 KB Output is correct
7 Correct 37 ms 504 KB Output is correct
8 Correct 39 ms 464 KB Output is correct
9 Correct 1119 ms 856 KB Output is correct
10 Correct 2440 ms 1052 KB Output is correct
11 Correct 4057 ms 1392 KB Output is correct
12 Correct 4370 ms 1304 KB Output is correct
13 Correct 59 ms 4256 KB Output is correct
14 Correct 64 ms 4044 KB Output is correct
15 Execution timed out 15076 ms 6456 KB Time limit exceeded
16 Halted 0 ms 0 KB -