oj.uz

Submission #500344

# Submission time Handle Problem Language Result Execution time Memory
500344 2021-12-30T18:54:19 Z 600Mihnea Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 6480 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) {

  struct Edge {
    int type;
    int x;
    int y;
    int id;
  };

  vector<Edge> edges;

  int m = (int)T.size();
  int q = (int)w.size();
  {
    map<pair<int, int>, int> inds;
    int kek = 0;
    for (int i = 0; i < m; i++) {
      if (X[i] > Y[i]) {
        swap(X[i], Y[i]);
      }
      if (!inds.count({X[i], Y[i]})) {
        inds[{X[i], Y[i]}] = ++kek;
      }
      edges.push_back({T[i], X[i], Y[i], inds[{X[i], Y[i]}]});
    }
  }

  function<bool(int, int)> cmp = [&] (int i, int j) {
    return p[i] < p[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(edges[step].x, edges[step].y);
          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(edges[step].x, edges[step].y);
        if (s.count(cur)) {
          s.erase(cur);
        } else {
          s.insert(cur);
        }
      }
    }
    for (int i = 0; i < m; i++) {
      swap(edges[i].x, edges[i].y);
      edges[i].x = n - 1 - edges[i].x;
      edges[i].y = n - 1 - edges[i].y;
    }
    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 284 ms 960 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 14 ms 460 KB Output is correct
4 Correct 22 ms 488 KB Output is correct
5 Correct 1269 ms 964 KB Output is correct
6 Correct 4797 ms 1496 KB Output is correct
7 Correct 44 ms 568 KB Output is correct
8 Correct 54 ms 520 KB Output is correct
9 Correct 1168 ms 984 KB Output is correct
10 Correct 2698 ms 1052 KB Output is correct
11 Correct 4865 ms 1516 KB Output is correct
12 Correct 5073 ms 1580 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 4728 KB Output is correct
2 Correct 97 ms 4764 KB Output is correct
3 Execution timed out 15023 ms 6480 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 4688 KB Output is correct
2 Correct 132 ms 4812 KB Output is correct
3 Correct 246 ms 4520 KB Output is correct
4 Correct 433 ms 4404 KB Output is correct
5 Correct 6008 ms 4080 KB Output is correct
6 Execution timed out 15074 ms 3668 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 960 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 14 ms 460 KB Output is correct
4 Correct 22 ms 488 KB Output is correct
5 Correct 1269 ms 964 KB Output is correct
6 Correct 4797 ms 1496 KB Output is correct
7 Correct 44 ms 568 KB Output is correct
8 Correct 54 ms 520 KB Output is correct
9 Correct 1168 ms 984 KB Output is correct
10 Correct 2698 ms 1052 KB Output is correct
11 Correct 4865 ms 1516 KB Output is correct
12 Correct 5073 ms 1580 KB Output is correct
13 Correct 61 ms 4728 KB Output is correct
14 Correct 97 ms 4764 KB Output is correct
15 Execution timed out 15023 ms 6480 KB Time limit exceeded
16 Halted 0 ms 0 KB -