oj.uz

Submission #993957

# Submission time Handle Problem Language Result Execution time Memory
993957 2024-06-06T21:42:37 Z MilosMilutinovic September (APIO24_september) C++17
0 / 100
 2 ms 600 KB 
#include "september.h"
#include <bits/stdc++.h>

using namespace std;

int solve(int n, int m, vector<int> par, vector<vector<int>> s) {
  vector<int> p(n);
  iota(p.begin(), p.end(), 0);
  vector<int> from(n, n), to(n, 0);
  function<int(int)> GetPar = [&](int x) {
    return p[x] == x ? x : p[x] = GetPar(p[x]);
  };
  auto Merge = [&](int x, int y) {
    x = GetPar(x);
    y = GetPar(y);
    if (x == y) {
      return;
    }
    from[x] = min(from[x], from[y]);
    to[x] = max(to[x], to[y]);
    p[y] = x;
  };
  for (int i = 0; i < m; i++) {
    for (int j = 0; j + 1 < n; j++) {
      from[s[i][j]] = min(from[s[i][j]], j);
      to[s[i][j]] = max(to[s[i][j]], j);
    }
  }
  vector<vector<int>> g(n);
  for (int i = 1; i < n; i++) {
    g[par[i]].push_back(i);
  }
  int T = 0;
  vector<int> dfn(n);
  vector<int> dfo(n);
  function<void(int)> Dfs = [&](int v) {
    dfn[v] = ++T;
    for (int u : g[v]) {
      Dfs(u);
    }
    dfo[v] = ++T; 
  };  
  Dfs(0);
  auto IsAnc = [&](int x, int y) {
    return dfn[x] <= dfn[y] && dfo[y] <= dfo[x];
  };
  for (int k = 0; k < m; k++) {
    vector<int> stk;
    for (int i = n - 2; i >= 0; i--) {
      vector<int> new_stk;
      for (int j : stk) {
        if (IsAnc(s[k][i], j)) {
          Merge(s[k][i], j);
        } else {
          new_stk.push_back(j);
        }
      }
      swap(stk, new_stk);
      stk.push_back(s[k][i]);
    }
  }
  vector<pair<int, int>> ev;
  for (int i = 1; i < n; i++) {
    if (GetPar(i) != i) {
      continue;
    }
    ev.emplace_back(from[i], ~to[i]);
    ev.emplace_back(to[i], to[i]);
  }
  sort(ev.begin(), ev.end());
  multiset<int> st;
  int res = 0;
  for (auto& p : ev) {
    if (st.empty()) {
      res += 1;
    }
    int v = p.second;
    if (v < 0) {
      st.insert(~v);
    } else {
      st.erase(st.find(v));
    }
  }
  return res;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #9
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -