oj.uz

답안 #500286

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500286 2021-12-30T15:34:15 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 M = 333;

vector<int> smart(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();

  vector<vector<int>> inds(m);
  for (int i = 0; i < q; i++) {
    inds[w[i]].push_back(i);
  }

  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());
  set<pair<int, int>> s;

  for (int step = 0; step < m; step++) {
    pair<int, int> cur = make_pair(x[step], y[step]);
    if (s.count(cur)) {
      s.erase(cur);
    } else {
      s.insert(cur);
    }
    for (auto &iq : inds[step]) {

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

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 278 ms 836 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 10 ms 428 KB Output is correct
4 Correct 17 ms 424 KB Output is correct
5 Correct 1212 ms 716 KB Output is correct
6 Correct 3880 ms 1240 KB Output is correct
7 Correct 27 ms 524 KB Output is correct
8 Correct 27 ms 460 KB Output is correct
9 Correct 1132 ms 860 KB Output is correct
10 Correct 2387 ms 912 KB Output is correct
11 Correct 4008 ms 1268 KB Output is correct
12 Correct 4275 ms 1240 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 3864 KB Output is correct
2 Correct 57 ms 4048 KB Output is correct
3 Execution timed out 15084 ms 6468 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 3860 KB Output is correct
2 Correct 74 ms 3876 KB Output is correct
3 Correct 155 ms 4040 KB Output is correct
4 Correct 331 ms 4056 KB Output is correct
5 Correct 5562 ms 3952 KB Output is correct
6 Execution timed out 15064 ms 4260 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 836 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 10 ms 428 KB Output is correct
4 Correct 17 ms 424 KB Output is correct
5 Correct 1212 ms 716 KB Output is correct
6 Correct 3880 ms 1240 KB Output is correct
7 Correct 27 ms 524 KB Output is correct
8 Correct 27 ms 460 KB Output is correct
9 Correct 1132 ms 860 KB Output is correct
10 Correct 2387 ms 912 KB Output is correct
11 Correct 4008 ms 1268 KB Output is correct
12 Correct 4275 ms 1240 KB Output is correct
13 Correct 49 ms 3864 KB Output is correct
14 Correct 57 ms 4048 KB Output is correct
15 Execution timed out 15084 ms 6468 KB Time limit exceeded
16 Halted 0 ms 0 KB -