Submission #342220

#	Time	Username	Problem	Language	Result	Execution time	Memory
342220		border	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2080 ms	13132 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 100010;
const int B = 315;
int n, m, q, d[N], b[N];
bool vis[N], busy[N];
vector<int> adj[N], rev[N];
vector<pair<int, int>> f[N];

void precompute() {
  for (int i = 1; i <= n; ++i) {
    vector<pair<int, int>> tmp;
    for (auto v: rev[i]) {
      for (auto x: f[v]) {
        tmp.push_back({x.first+1, x.second});
      }
    }
    tmp.push_back({0, i});
    sort(tmp.begin(), tmp.end(), greater<pair<int, int>>());
    for (auto x: tmp) {
      if (!vis[x.second]) {
        vis[x.second] = true;
        f[i].push_back(x);
        if (f[i].size() == B) break;
      }
    }
    for (auto p: f[i]) vis[p.second] = false;
  }
}

int solve(int source) {
  int ans = -1;
  for (auto x: f[source]) {
    if (!busy[x.second]) {
      ans = max(ans, x.first);
    }
  }
  return ans;
}

int brute(int source) {
  for (int i = 1; i <= n; ++i) d[i] = INT_MIN;
  d[source] = 0;
  for (int i = source-1; i >= 1; --i) {
    for (auto v: adj[i]) {
      d[i] = max(d[i], d[v] + 1);
    }
  }
  int ans = -1;
  for (int i = 1; i <= source; ++i) {
    if (!busy[i]) ans = max(ans, d[i]);
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m >> q;
  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    rev[v].push_back(u);
  }

  precompute();
  while (q--) {
    int node, sz;
    cin >> node >> sz;
    for (int i = 1; i <= sz; ++i) {
      cin >> b[i];
      busy[b[i]] = true;
    }
    if (sz >= B) {
      cout << brute(node) << '\n';
    } else {
      cout << solve(node) << '\n';
    }
    for (int i = 1; i <= sz; ++i) {
      busy[b[i]] = false;
    }
  }
}

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