oj.uz

Submission #500369

# Submission time Handle Problem Language Result Execution time Memory
500369 2021-12-30T19:40:26 Z 600Mihnea Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 6976 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);
  modif[id].push_back(a);
  modif[id].push_back(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();
  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]);
          }
        }
        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);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1740 KB Output is correct
2 Correct 66 ms 1372 KB Output is correct
3 Correct 291 ms 1604 KB Output is correct
4 Correct 902 ms 2464 KB Output is correct
5 Correct 54 ms 1844 KB Output is correct
6 Correct 521 ms 2488 KB Output is correct
7 Correct 106 ms 1404 KB Output is correct
8 Correct 236 ms 1612 KB Output is correct
9 Correct 89 ms 2020 KB Output is correct
10 Correct 445 ms 2440 KB Output is correct
11 Correct 599 ms 2728 KB Output is correct
12 Correct 528 ms 2508 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 5244 KB Output is correct
2 Execution timed out 15087 ms 6416 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 5116 KB Output is correct
2 Execution timed out 15086 ms 6976 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 66 ms 1372 KB Output is correct
3 Correct 291 ms 1604 KB Output is correct
4 Correct 902 ms 2464 KB Output is correct
5 Correct 54 ms 1844 KB Output is correct
6 Correct 521 ms 2488 KB Output is correct
7 Correct 106 ms 1404 KB Output is correct
8 Correct 236 ms 1612 KB Output is correct
9 Correct 89 ms 2020 KB Output is correct
10 Correct 445 ms 2440 KB Output is correct
11 Correct 599 ms 2728 KB Output is correct
12 Correct 528 ms 2508 KB Output is correct
13 Correct 49 ms 5244 KB Output is correct
14 Execution timed out 15087 ms 6416 KB Time limit exceeded
15 Halted 0 ms 0 KB -