Submission #342222

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

bitaro

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 100010;
const int B = 215;
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() {
  vector<pair<int, int>> tmp;
  for (int i = 1; i <= n; ++i) {
    tmp.clear();
    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>>());
    int sz = f[i].size();
    for (auto x: tmp) {
      if (!vis[x.second]) {
        vis[x.second] = true;
        f[i].push_back(x);
        sz++;
        if (sz == 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() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= m; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    adj[u].push_back(v);
    rev[v].push_back(u);
  }

  precompute();
  while (q--) {
    int node, sz;
    scanf("%d%d", &node, &sz);
    for (int i = 1; i <= sz; ++i) {
      scanf("%d", &b[i]);
      busy[b[i]] = true;
    }
    if (sz >= B) {
      printf("%d\n", brute(node));
    } else {
      printf("%d\n", solve(node));
    }
    for (int i = 1; i <= sz; ++i) {
      busy[b[i]] = false;
    }
  }
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |   scanf("%d%d%d", &n, &m, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |     scanf("%d%d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |     scanf("%d%d", &node, &sz);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
bitaro.cpp:75:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |       scanf("%d", &b[i]);
      |       ~~~~~^~~~~~~~~~~~~

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