Submission #220886

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

bitaro

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

const int MAXN = 100005;
const int BLOCK = 305;

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

int dp[MAXN];
bool cannot_visit[MAXN];

int in_ans[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);
  in_ans[n] = 0;

  for (auto i : radj[n]) {
    Preprocess(i);
    for (auto j : ans[i]) {
      if (in_ans[j.first] == -1) {
        in_ans[j.first] = ans[n].size();
        ans[n].emplace_back(j.first, j.second + 1);
      } else {
        ans[n][in_ans[j.first]] = max(ans[n][in_ans[j.first]], make_pair(j.first, j.second + 1));
      }
    }
  }

  for (auto i : ans[n]) {
    in_ans[i.first] = -1;
  }

  nth_element(begin(ans[n]), begin(ans[n]) + BLOCK, 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 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 Preprocess() {
  memset(in_ans, -1, sizeof(in_ans));
  mark++;
  for (int i = 1; i <= N; i++) {
    Preprocess(i);
  }
}

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;
    }

    int res = -1;
    
    if (C.size() >= BLOCK) {
      mark++; Dfs(T);
      res = max(res, dp[T]) ;
    } else {
      for (int j = 0; j < ans[T].size(); j++) {
        int u = ans[T][j].first;
        if (cannot_visit[u]) continue;
        res = max(res, ans[T][j].second);
      }
    }

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

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

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

Compilation message (stderr)

bitaro.cpp: In function 'void Solve()':
bitaro.cpp:94: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: 86 / 86