oj.uz

Submission #993948

# Submission time Handle Problem Language Result Execution time Memory
993948 2024-06-06T21:27:02 Z MilosMilutinovic September (APIO24_september) C++17
35 / 100
 1000 ms 1368 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++) {
    for (int i = 0; i + 1 < n; i++) {
      for (int j = i + 1; j + 1 < n; j++) {
        if (IsAnc(s[k][i], s[k][j])) {
          Merge(s[k][i], s[k][j]);
        }
      }
    }
  }
  for (int i = 1; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (GetPar(i) != i || GetPar(j) != j) {
        continue;
      }
      if (to[i] < from[j] || to[j] < from[i]) {
        continue;
      }
      Merge(i, j);
    }
  }
  int res = 0;
  for (int i = 1; i < n; i++) {
    res += (GetPar(i) == i);
  }
  return res;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 608 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 5 ms 604 KB Output is correct

Subtask #4
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 5 ms 608 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Incorrect 6 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 608 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 8 ms 604 KB Output is correct
5 Correct 8 ms 604 KB Output is correct
6 Correct 8 ms 648 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 5 ms 608 KB Output is correct
16 Correct 5 ms 604 KB Output is correct
17 Correct 5 ms 604 KB Output is correct
18 Incorrect 6 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #7
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 608 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Execution timed out 1034 ms 1368 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #8
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 5 ms 608 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Incorrect 6 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #9
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 608 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 8 ms 604 KB Output is correct
5 Correct 8 ms 604 KB Output is correct
6 Correct 8 ms 648 KB Output is correct
7 Execution timed out 1034 ms 1368 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #10
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 5 ms 608 KB Output is correct
16 Correct 5 ms 604 KB Output is correct
17 Correct 5 ms 604 KB Output is correct
18 Incorrect 6 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -