oj.uz

Submission #500381

# Submission time Handle Problem Language Result Execution time Memory
500381 2021-12-30T19:54:56 Z 600Mihnea Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 15648 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 = 400;

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 19 ms 1740 KB Output is correct
2 Correct 37 ms 1336 KB Output is correct
3 Correct 166 ms 1452 KB Output is correct
4 Correct 473 ms 1884 KB Output is correct
5 Correct 42 ms 1740 KB Output is correct
6 Correct 424 ms 2280 KB Output is correct
7 Correct 53 ms 1316 KB Output is correct
8 Correct 129 ms 1508 KB Output is correct
9 Correct 68 ms 1880 KB Output is correct
10 Correct 318 ms 2204 KB Output is correct
11 Correct 426 ms 2296 KB Output is correct
12 Correct 405 ms 2496 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 5048 KB Output is correct
2 Correct 13957 ms 5756 KB Output is correct
3 Correct 1559 ms 15648 KB Output is correct
4 Execution timed out 15092 ms 9116 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 5180 KB Output is correct
2 Execution timed out 15092 ms 5892 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1740 KB Output is correct
2 Correct 37 ms 1336 KB Output is correct
3 Correct 166 ms 1452 KB Output is correct
4 Correct 473 ms 1884 KB Output is correct
5 Correct 42 ms 1740 KB Output is correct
6 Correct 424 ms 2280 KB Output is correct
7 Correct 53 ms 1316 KB Output is correct
8 Correct 129 ms 1508 KB Output is correct
9 Correct 68 ms 1880 KB Output is correct
10 Correct 318 ms 2204 KB Output is correct
11 Correct 426 ms 2296 KB Output is correct
12 Correct 405 ms 2496 KB Output is correct
13 Correct 53 ms 5048 KB Output is correct
14 Correct 13957 ms 5756 KB Output is correct
15 Correct 1559 ms 15648 KB Output is correct
16 Execution timed out 15092 ms 9116 KB Time limit exceeded
17 Halted 0 ms 0 KB -