oj.uz

Submission #500284

# Submission time Handle Problem Language Result Execution time Memory
500284 2021-12-30T15:28:36 Z 600Mihnea Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 7828 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;
}


vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
	return brute(N,T,X,Y,W,P);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 588 KB Output is correct
2 Correct 3 ms 432 KB Output is correct
3 Correct 7 ms 460 KB Output is correct
4 Correct 14 ms 452 KB Output is correct
5 Correct 1078 ms 668 KB Output is correct
6 Correct 3324 ms 1132 KB Output is correct
7 Correct 13 ms 420 KB Output is correct
8 Correct 16 ms 420 KB Output is correct
9 Correct 1041 ms 716 KB Output is correct
10 Correct 2170 ms 836 KB Output is correct
11 Correct 3220 ms 1264 KB Output is correct
12 Correct 3401 ms 1340 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3388 KB Output is correct
2 Correct 45 ms 3380 KB Output is correct
3 Execution timed out 15060 ms 7828 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3300 KB Output is correct
2 Correct 56 ms 3368 KB Output is correct
3 Correct 120 ms 3480 KB Output is correct
4 Correct 243 ms 3404 KB Output is correct
5 Correct 4269 ms 3744 KB Output is correct
6 Execution timed out 15070 ms 4796 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 588 KB Output is correct
2 Correct 3 ms 432 KB Output is correct
3 Correct 7 ms 460 KB Output is correct
4 Correct 14 ms 452 KB Output is correct
5 Correct 1078 ms 668 KB Output is correct
6 Correct 3324 ms 1132 KB Output is correct
7 Correct 13 ms 420 KB Output is correct
8 Correct 16 ms 420 KB Output is correct
9 Correct 1041 ms 716 KB Output is correct
10 Correct 2170 ms 836 KB Output is correct
11 Correct 3220 ms 1264 KB Output is correct
12 Correct 3401 ms 1340 KB Output is correct
13 Correct 28 ms 3388 KB Output is correct
14 Correct 45 ms 3380 KB Output is correct
15 Execution timed out 15060 ms 7828 KB Time limit exceeded
16 Halted 0 ms 0 KB -