oj.uz

Submission #500379

# Submission time Handle Problem Language Result Execution time Memory
500379 2021-12-30T19:53:27 Z 600Mihnea Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 15692 KB 
#include "collapse.h"
#include <bits/stdc++.h>

using namespace std;

const int NN = 100000 + 7;

int dsu[2][NN], un[2];

vector<int> modif[2];

void clr(int id) {
  modif[id].clear();
  assert(0 <= id && id < 2);
  un[id] = 0;
  for (int i = 0; i < NN; i++) {
    dsu[id][i] = i;
  }
}

void restore(int id) {
  un[id] = 0;
  for (auto &i : modif[id]) {
    dsu[id][i] = i;
  }
}

int root(int id, int a) {

  if (a == dsu[id][a]) {
    return a;
  } else {
    return dsu[id][a] = root(id, dsu[id][a]);
  }
}

void unite(int id, int a, int b) {
  if (id) {
    modif[id].push_back(a);
    modif[id].push_back(b);
  }
  a = root(id, a);
  b = root(id, b);
  if (a != b) {
    un[id]++;
    dsu[id][a] = b;
  }
}

const int edgeM = 200;

vector<int> smart(int n, vector<int> T, vector<int> X, vector<int> Y, vector<int> w, vector<int> p) {
  clr(0);
  clr(1);
  struct Edge {
    int type;
    int x;
    int y;
    int id;
  };

  vector<Edge> edges;

  int m = (int)T.size();
  int q = (int)w.size();
  bool ok = (n <= 5000 && q <= 5000 && m <= 5000);
  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++) {
      clr(0);
      clr(1);
      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) {
        restore(1);
        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]);
          }
        }
        //if (!ok) continue;
        for (int step = edgeFirst[edgeBucketId]; step <= w[iq]; step++) {
          current[edges[step].id] = active[edges[step].id];
        }
        while (ptr < (int) additional.size() && additional[ptr].second <= p[iq]) {
          unite(0, additional[ptr].first, additional[ptr].second);
          ptr++;
        }
        for (auto &it : specific) {
          if (it.second <= p[iq]) {
            unite(1, root(0, it.first), root(0, it.second));
          }
        }
        sol[iq] += p[iq] + 1 - (un[0] + un[1]);
      }
      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) {
	return smart(N,T,X,Y,W,P);
}

Compilation message

collapse.cpp: In function 'std::vector<int> smart(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:66:8: warning: unused variable 'ok' [-Wunused-variable]
   66 |   bool ok = (n <= 5000 && q <= 5000 && m <= 5000);
      |        ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1740 KB Output is correct
2 Correct 35 ms 1340 KB Output is correct
3 Correct 149 ms 1648 KB Output is correct
4 Correct 460 ms 1892 KB Output is correct
5 Correct 37 ms 1796 KB Output is correct
6 Correct 126 ms 2192 KB Output is correct
7 Correct 49 ms 1304 KB Output is correct
8 Correct 124 ms 1380 KB Output is correct
9 Correct 40 ms 1820 KB Output is correct
10 Correct 120 ms 1940 KB Output is correct
11 Correct 134 ms 2152 KB Output is correct
12 Correct 134 ms 2124 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5000 KB Output is correct
2 Correct 13647 ms 6016 KB Output is correct
3 Correct 887 ms 15692 KB Output is correct
4 Execution timed out 15082 ms 9200 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 5120 KB Output is correct
2 Execution timed out 15073 ms 5992 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1740 KB Output is correct
2 Correct 35 ms 1340 KB Output is correct
3 Correct 149 ms 1648 KB Output is correct
4 Correct 460 ms 1892 KB Output is correct
5 Correct 37 ms 1796 KB Output is correct
6 Correct 126 ms 2192 KB Output is correct
7 Correct 49 ms 1304 KB Output is correct
8 Correct 124 ms 1380 KB Output is correct
9 Correct 40 ms 1820 KB Output is correct
10 Correct 120 ms 1940 KB Output is correct
11 Correct 134 ms 2152 KB Output is correct
12 Correct 134 ms 2124 KB Output is correct
13 Correct 46 ms 5000 KB Output is correct
14 Correct 13647 ms 6016 KB Output is correct
15 Correct 887 ms 15692 KB Output is correct
16 Execution timed out 15082 ms 9200 KB Time limit exceeded
17 Halted 0 ms 0 KB -