Submission #500339

#	Time	Username	Problem	Language	Result	Execution time	Memory
500339		600Mihnea	Collapse (JOI18_collapse)	C++17	5 / 100	15092 ms	6476 KiB

collapse

#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 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35