oj.uz

Submission #500394

# Submission time Handle Problem Language Result Execution time Memory
500394 2021-12-30T20:12:29 Z 600Mihnea Collapse (JOI18_collapse) C++17
0 / 100
 900 ms 15596 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 NN = 100000 + 7;
int dsu[2][NN], un[2], lt[2][NN], tt;


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

int root(int id, int a) {
  if (lt[id][a] != tt) {
    dsu[id][a] = a;
    lt[id][a] = tt;
  }
  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 == 1) {

 // }
  a = root(id, a);
  b = root(id, b);
  if (id) {
    lt[id][a] = tt;
    lt[id][b] = tt;
  }
  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++) {
     // cout << ISTEP << ", " << edgeBucketId << " out of " << edgeBucket[m - 1] << "\n";
      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) {
        tt++;
        un[1] = 0;
        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++;
        }
      //  assert((int) specific.size() <= edgeM);
        //if (!ok) continue;

        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) {
  auto x = smart(N,T,X,Y,W,P);return x;
  auto y = brute(N,T,X,Y,W,P);
  int dif = 0, good = 0;
  for (int i = 0; i < (int) x.size(); i++) {
    dif += (x[i] != y[i]);
    good += (x[i] == y[i]);
  }
  cout << good << ", " << dif << "\n";
  assert(x==y);
  exit(0);
	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:126:8: warning: unused variable 'ok' [-Wunused-variable]
  126 |   bool ok = (n <= 5000 && q <= 5000 && m <= 5000);
      |        ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1740 KB Output is correct
2 Correct 4 ms 1228 KB Output is correct
3 Correct 6 ms 1228 KB Output is correct
4 Correct 9 ms 1228 KB Output is correct
5 Correct 23 ms 1740 KB Output is correct
6 Incorrect 64 ms 1996 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 5032 KB Output is correct
2 Correct 52 ms 5300 KB Output is correct
3 Incorrect 467 ms 15596 KB Output isn't correct
4 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 Correct 66 ms 5220 KB Output is correct
3 Correct 105 ms 5476 KB Output is correct
4 Correct 162 ms 5548 KB Output is correct
5 Incorrect 900 ms 5304 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1740 KB Output is correct
2 Correct 4 ms 1228 KB Output is correct
3 Correct 6 ms 1228 KB Output is correct
4 Correct 9 ms 1228 KB Output is correct
5 Correct 23 ms 1740 KB Output is correct
6 Incorrect 64 ms 1996 KB Output isn't correct
7 Halted 0 ms 0 KB -