Submission #220878

#	Time	Username	Problem	Language	Result	Execution time	Memory
220878		rama_pang	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2088 ms	97016 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int BLOCK = 45;

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]; // BLOCK 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() > BLOCK) 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;

    vector<int> C(Y);
    for (auto &c : C) {
      cin >> c;
      cannot_visit[c] = true;
    }

    if (C.size() >= BLOCK) {
      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 (cannot_visit[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:88:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < ans[T].size(); j++) {
                       ~~^~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 0 / 86