oj.uz

Submission #500378

# Submission time Handle Problem Language Result Execution time Memory
500378 2021-12-30T19:51:46 Z 600Mihnea Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 15612 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) {
  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 = 333;

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:64:8: warning: unused variable 'ok' [-Wunused-variable]
   64 |   bool ok = (n <= 5000 && q <= 5000 && m <= 5000);
      |        ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1740 KB Output is correct
2 Correct 16 ms 1308 KB Output is correct
3 Correct 153 ms 1480 KB Output is correct
4 Correct 460 ms 1888 KB Output is correct
5 Correct 39 ms 1740 KB Output is correct
6 Correct 284 ms 2236 KB Output is correct
7 Correct 53 ms 1332 KB Output is correct
8 Correct 125 ms 1376 KB Output is correct
9 Correct 53 ms 1856 KB Output is correct
10 Correct 250 ms 2200 KB Output is correct
11 Correct 305 ms 2320 KB Output is correct
12 Correct 290 ms 2256 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 5048 KB Output is correct
2 Correct 13770 ms 5756 KB Output is correct
3 Correct 1349 ms 15612 KB Output is correct
4 Execution timed out 15069 ms 9640 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5048 KB Output is correct
2 Execution timed out 15019 ms 6156 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1740 KB Output is correct
2 Correct 16 ms 1308 KB Output is correct
3 Correct 153 ms 1480 KB Output is correct
4 Correct 460 ms 1888 KB Output is correct
5 Correct 39 ms 1740 KB Output is correct
6 Correct 284 ms 2236 KB Output is correct
7 Correct 53 ms 1332 KB Output is correct
8 Correct 125 ms 1376 KB Output is correct
9 Correct 53 ms 1856 KB Output is correct
10 Correct 250 ms 2200 KB Output is correct
11 Correct 305 ms 2320 KB Output is correct
12 Correct 290 ms 2256 KB Output is correct
13 Correct 47 ms 5048 KB Output is correct
14 Correct 13770 ms 5756 KB Output is correct
15 Correct 1349 ms 15612 KB Output is correct
16 Execution timed out 15069 ms 9640 KB Time limit exceeded
17 Halted 0 ms 0 KB -