oj.uz

Submission #500361

# Submission time Handle Problem Language Result Execution time Memory
500361 2021-12-30T19:23:36 Z 600Mihnea Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 6468 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();
  vector<pair<int, int>> theEdge;
  vector<int> active;
  {
    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++;
        theEdge.push_back({X[i], Y[i]});
        active.push_back(0);
      }
      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];
  };

  function<bool(int, int)> cmpE = [&] (int i, int j) {
    return theEdge[i].second < theEdge[j].second;
  };

  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++) {
    for (auto &x : active) {
      x = 0;
    }
    vector<int> edgeBucket(m), edgeFirst(m), edgeLast(m);

    vector<int> O;

    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);
    }

    vector<int> order((int) active.size());
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), cmpE);


    for (int edgeBucketId = edgeBucket[0]; edgeBucketId <= edgeBucket[m - 1]; edgeBucketId++) {
      vector<bool> use_now((int) active.size(), 0);
      vector<int> current = active;
      vector<int> guys;
      for (int step = edgeFirst[edgeBucketId]; step <= edgeLast[edgeBucketId]; step++) {
        use_now[edges[step].id] = 1;
        for (auto &iq : inds[step]) {
          guys.push_back(iq);
        }
      }
      vector<pair<int, int>> additional;
      vector<int> here;
      for (auto &i : order) {
        if (use_now[i]) {
          here.push_back(i);
        }
        if (active[i] && !use_now[i]) {
          additional.push_back(theEdge[i]);
        }
      }
      int ptr = 0;
      sort(guys.begin(), guys.end(), cmp);
      for (auto &iq : guys) {
        for (int step = edgeFirst[edgeBucketId]; step <= w[iq]; step++) {
          current[edges[step].id] ^= 1;
        }
        vector<pair<int, int>> specific;
        for (auto &i : here) {
          if (current[i]) {
            specific.push_back(theEdge[i]);
          }
        }
        for (int step = edgeFirst[edgeBucketId]; step <= w[iq]; step++) {
          current[edges[step].id] = active[edges[step].id];
        }
        vector<pair<int, int>> ve;
        while (ptr < (int) additional.size() && additional[ptr].second <= p[iq]) {
          ptr++;
        }
        for (int j = 0; j < ptr; j++) {
          ve.push_back(additional[j]);
        }
        for (auto &it : specific) {
          if (it.second <= p[iq]) {
            ve.push_back(it);
            continue;
          }
        }
        vector<int> t(n);
        iota(t.begin(), t.end(), 0);
        int united = 0;
        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) {
            united++;
            t[a] = b;
          }
        };
        for (auto &it : ve) {
          unite(it.first, it.second);
        }
        sol[iq] += p[iq] + 1 - united;
      }
      for (int step = edgeFirst[edgeBucketId]; step <= edgeLast[edgeBucketId]; step++) {
        active[edges[step].id] ^= 1;
      }
    }
    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];
    }
    for (auto &it : theEdge) {
      swap(it.first, it.second);
      it.first = n - 1 - it.first;
      it.second = n - 1 - it.second;
    }
  }
  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 207 ms 964 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 11 ms 492 KB Output is correct
4 Correct 21 ms 428 KB Output is correct
5 Correct 1092 ms 964 KB Output is correct
6 Correct 3629 ms 1460 KB Output is correct
7 Correct 37 ms 528 KB Output is correct
8 Correct 43 ms 540 KB Output is correct
9 Correct 1025 ms 1004 KB Output is correct
10 Correct 2241 ms 1056 KB Output is correct
11 Correct 3584 ms 1316 KB Output is correct
12 Correct 3801 ms 1408 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 4716 KB Output is correct
2 Correct 84 ms 4680 KB Output is correct
3 Execution timed out 15043 ms 6468 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 4652 KB Output is correct
2 Correct 114 ms 4788 KB Output is correct
3 Correct 192 ms 4428 KB Output is correct
4 Correct 350 ms 4304 KB Output is correct
5 Correct 5161 ms 4084 KB Output is correct
6 Execution timed out 15071 ms 3780 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 964 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 11 ms 492 KB Output is correct
4 Correct 21 ms 428 KB Output is correct
5 Correct 1092 ms 964 KB Output is correct
6 Correct 3629 ms 1460 KB Output is correct
7 Correct 37 ms 528 KB Output is correct
8 Correct 43 ms 540 KB Output is correct
9 Correct 1025 ms 1004 KB Output is correct
10 Correct 2241 ms 1056 KB Output is correct
11 Correct 3584 ms 1316 KB Output is correct
12 Correct 3801 ms 1408 KB Output is correct
13 Correct 58 ms 4716 KB Output is correct
14 Correct 84 ms 4680 KB Output is correct
15 Execution timed out 15043 ms 6468 KB Time limit exceeded
16 Halted 0 ms 0 KB -