Submission #993948

#	Time	Username	Problem	Language	Result	Execution time	Memory
993948		MilosMilutinovic	September (APIO24_september)	C++17	35 / 100	1034 ms	1368 KiB

september

#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 / 11
• Subtask 2: 14 / 14
• Subtask 3: 5 / 5
• Subtask 4: 0 / 9
• Subtask 5: 5 / 5
• Subtask 6: 0 / 11
• Subtask 7: 0 / 9
• Subtask 8: 0 / 11
• Subtask 9: 0 / 9
• Subtask 10: 0 / 16