Submission #220864

#TimeUsernameProblemLanguageResultExecution timeMemory
220864rama_pangBitaro’s Party (JOI18_bitaro)C++14
7 / 100
2101 ms183348 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int SQRT = MAXN / log2(MAXN) + 1;

int N, M, Q;
vector<int> radj[MAXN];
int vis[MAXN], mark = 0;

int dp[MAXN];
bool cannot_visit[MAXN];
vector<pair<int, int>> ans[MAXN]; // sqrt N longest paths from a vertex (city, length)

void Read() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> M >> Q;
  for (int i = 0; i < M; i++) {
    int S, E;
    cin >> S >> E;
    radj[E].emplace_back(S);
  }
}

void Preprocess(int n) {
  if (vis[n] == mark) return;
  vis[n] = mark;
  ans[n].emplace_back(n, 0);
  for (auto i : radj[n]) {
    Preprocess(i);
    for (auto j : ans[i]) {
      ans[n].emplace_back(j.first, j.second + 1);
    }
  }

  sort(begin(ans[n]), end(ans[n]), [&](const pair<int, int> &a, const pair<int, int> &b) {
    return a.first < b.first || (a.first == b.first && a.second > b.second);
  });

  ans[n].resize(unique(begin(ans[n]), end(ans[n]), [&](const pair<int, int> &a, const pair<int, int> &b) {
    return a.first == b.first;
  }) - begin(ans[n]));

  sort(begin(ans[n]), end(ans[n]), [&](const pair<int, int> &a, const pair<int, int> &b) {
    return a.second > b.second;
  });

  while (ans[n].size() > SQRT) ans[n].pop_back();
}

void Preprocess() {
  mark++;
  for (int i = 1; i <= N; i++) {
    Preprocess(i);
  }
}

void Dfs(int n) {
  if (vis[n] == mark) return;
  vis[n] = mark;
  dp[n] = (cannot_visit[n] ? -1e9 : 0);
  for (auto i : radj[n]) {
    Dfs(i);
    dp[n] = max(dp[n], dp[i] + 1);
  }
}

void Solve() {
  for (int i = 0; i < Q; i++) {
    int T, Y;
    cin >> T >> Y;

    set<int> C;
    while (Y--) {
      int c;
      cin >> c;
      C.emplace(c);
      cannot_visit[c] = true;
    }

    if (C.size() >= SQRT) {
      mark++; Dfs(T);
      cout << max(dp[T], -1) << "\n";
    } else {
      int res = -1;

      for (int j = 0; j < ans[T].size(); j++) {
        int u = ans[T][j].first;
        if (C.count(u)) continue;
        res = ans[T][j].second;
        break;
      }

      cout << res << "\n";
    }

    for (auto c : C) {
      cannot_visit[c] = false;
    }
  }
}

int main() {
  Read();
  Preprocess();
  Solve();
  return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void Solve()':
bitaro.cpp:89:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < ans[T].size(); j++) {
                       ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...