oj.uz

답안 #500355

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500355 2021-12-30T19:15:01 Z 600Mihnea Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 6468 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 edgeM = 333;
const int edgeM = 7;

vector<int> smart(int n, vector<int> T, vector<int> X, vector<int> Y, vector<int> w, vector<int> p) {

  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];
  };

  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);


    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);
    }


    set<pair<int, int>> s;
    for (int edgeBucketId = edgeBucket[0]; edgeBucketId <= edgeBucket[m - 1]; edgeBucketId++) {
      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 (int i = 0; i < (int) active.size(); i++) {
        if (use_now[i]) {
          here.push_back(i);
        }
        if (active[i] && !use_now[i]) {
          additional.push_back(theEdge[i]);
        }
      }
      sort(guys.begin(), guys.end(), cmp);
      set<pair<int, int>> cop = s;
      for (auto &iq : guys) {
        s = cop;
        for (int step = edgeFirst[edgeBucketId]; step <= w[iq]; step++) {
          pair<int, int> cur = make_pair(edges[step].x, edges[step].y);
          current[edges[step].id] ^= 1;
          if (s.count(cur)) {
            s.erase(cur);
          } else {
            s.insert(cur);
          }
        }
        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];
        }
        vector<pair<int, int>> ve;
        for (auto &it : additional) {
          if (it.second <= p[iq]) {
            ve.push_back(it);
            continue;
          }
        }
        for (auto &it : specific) {
          if (it.second <= p[iq]) {
            ve.push_back(it);
            continue;
          }
        }
        vector<int> t(n);
        iota(t.begin(), t.end(), 0);
        int comps = p[iq] + 1;
        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;
      }
      s = cop;
      for (int step = edgeFirst[edgeBucketId]; step <= edgeLast[edgeBucketId]; step++) {
        pair<int, int> cur = make_pair(edges[step].x, edges[step].y);
        active[edges[step].id] ^= 1;
        if (s.count(cur)) {
          s.erase(cur);
        } else {
          s.insert(cur);
        }
      }
    }
    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 B=brute(N,T,X,Y,W,P);
	auto S=smart(N,T,X,Y,W,P);


	assert(B==S);
	return S;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 323 ms 960 KB Output is correct
2 Correct 6 ms 460 KB Output is correct
3 Correct 13 ms 460 KB Output is correct
4 Correct 21 ms 460 KB Output is correct
5 Correct 1171 ms 968 KB Output is correct
6 Correct 4399 ms 1748 KB Output is correct
7 Correct 36 ms 444 KB Output is correct
8 Correct 41 ms 464 KB Output is correct
9 Correct 1158 ms 1092 KB Output is correct
10 Correct 2448 ms 1168 KB Output is correct
11 Correct 4506 ms 1992 KB Output is correct
12 Correct 4887 ms 1932 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 4712 KB Output is correct
2 Correct 103 ms 4672 KB Output is correct
3 Execution timed out 15070 ms 6468 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 4660 KB Output is correct
2 Correct 156 ms 4912 KB Output is correct
3 Correct 248 ms 4468 KB Output is correct
4 Correct 427 ms 4384 KB Output is correct
5 Correct 5773 ms 4080 KB Output is correct
6 Execution timed out 15054 ms 3864 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 323 ms 960 KB Output is correct
2 Correct 6 ms 460 KB Output is correct
3 Correct 13 ms 460 KB Output is correct
4 Correct 21 ms 460 KB Output is correct
5 Correct 1171 ms 968 KB Output is correct
6 Correct 4399 ms 1748 KB Output is correct
7 Correct 36 ms 444 KB Output is correct
8 Correct 41 ms 464 KB Output is correct
9 Correct 1158 ms 1092 KB Output is correct
10 Correct 2448 ms 1168 KB Output is correct
11 Correct 4506 ms 1992 KB Output is correct
12 Correct 4887 ms 1932 KB Output is correct
13 Correct 66 ms 4712 KB Output is correct
14 Correct 103 ms 4672 KB Output is correct
15 Execution timed out 15070 ms 6468 KB Time limit exceeded
16 Halted 0 ms 0 KB -