oj.uz

Submission #500339

# Submission time Handle Problem Language Result Execution time Memory
500339 2021-12-30T18:47:24 Z 600Mihnea Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 6476 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);
    }
  }

  function<bool(int, int)> cmp = [&] (int i, int j) {
    return y[i] < y[j];
  };

  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++) {
      vector<int> guys;
      for (int step = edgeFirst[edgeBucketId]; step <= edgeLast[edgeBucketId]; step++) {
        for (auto &iq : inds[step]) {
          guys.push_back(iq);
        }
      }
      sort(guys.begin(), guys.end(), cmp);
      set<pair<int, int>> cop = s;
      for (auto &iq : guys) {
        s = cop;
        for (int step = edgeFirst[edgeBucketId]; step <= w[iq]; step++) {
          pair<int, int> cur = make_pair(x[step], y[step]);
          if (s.count(cur)) {
            s.erase(cur);
          } else {
            s.insert(cur);
          }
        }
        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;
      }
      s = cop;
      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 (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 270 ms 840 KB Output is correct
2 Correct 6 ms 536 KB Output is correct
3 Correct 14 ms 460 KB Output is correct
4 Correct 23 ms 460 KB Output is correct
5 Correct 1147 ms 840 KB Output is correct
6 Correct 4622 ms 1468 KB Output is correct
7 Correct 36 ms 460 KB Output is correct
8 Correct 40 ms 540 KB Output is correct
9 Correct 1197 ms 860 KB Output is correct
10 Correct 2459 ms 920 KB Output is correct
11 Correct 4882 ms 1480 KB Output is correct
12 Correct 5020 ms 1536 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 4664 KB Output is correct
2 Correct 107 ms 4804 KB Output is correct
3 Execution timed out 15019 ms 6476 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4660 KB Output is correct
2 Correct 134 ms 4804 KB Output is correct
3 Correct 233 ms 4568 KB Output is correct
4 Correct 448 ms 4316 KB Output is correct
5 Correct 6200 ms 4056 KB Output is correct
6 Execution timed out 15092 ms 3620 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 840 KB Output is correct
2 Correct 6 ms 536 KB Output is correct
3 Correct 14 ms 460 KB Output is correct
4 Correct 23 ms 460 KB Output is correct
5 Correct 1147 ms 840 KB Output is correct
6 Correct 4622 ms 1468 KB Output is correct
7 Correct 36 ms 460 KB Output is correct
8 Correct 40 ms 540 KB Output is correct
9 Correct 1197 ms 860 KB Output is correct
10 Correct 2459 ms 920 KB Output is correct
11 Correct 4882 ms 1480 KB Output is correct
12 Correct 5020 ms 1536 KB Output is correct
13 Correct 66 ms 4664 KB Output is correct
14 Correct 107 ms 4804 KB Output is correct
15 Execution timed out 15019 ms 6476 KB Time limit exceeded
16 Halted 0 ms 0 KB -