Submission #484203

#	Time	Username	Problem	Language	Result	Execution time	Memory
484203		ian2024	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	2099 ms	5068 KiB

bitaro

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

#ifdef LOCAL_PROJECT
#else
#define cerr \
  if (false) cerr
#endif

#define f first
#define s second
#define pb push_back

#define all(x) x.begin(), x.end()
#define ALL(x) begin(x), end(x)
#define FOR(i, a) for (int i = 0; i < (a); i++)
#define SZ(a) (int)(a).size()

typedef pair<int, int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;
typedef vector<ll> vll;

const int INF = 1e9;
const ll INFL = 1e18;
const int MOD = 1000000007;
const int sz = 1e5 + 5;

vi adj[sz];
int k;
bool vis[sz];
ii towns[sz][320];

void dfs(int u, int p) {
  for (auto v : adj[u]) {
    if (v != p) dfs(v, u);
  }

  vii paths;
  for (auto v : adj[u]) {
    if (v == p) continue;
    for (int i = 0; i < k; ++i) {
      if (towns[v][i].s == 0) break;
      paths.pb({1 + towns[v][i].f, towns[v][i].s});
    }
    paths.pb({1, v});
  }

  sort(all(paths), greater<ii>());
  
  set<int> chosen;
  int curr = 0;
  int i = 0;
  while (curr < k and i < SZ(paths)) {
    if (chosen.find(paths[i].s) != chosen.end()) {
      i++;
      continue;
    }

    towns[u][curr] = paths[i];
    chosen.insert(paths[i].s);
    // cerr << paths[i].f << " " << paths[i].s << endl;
    i++;
    curr++;
  }
  vis[u] = true;
}

int dfs2(int u, int p, vi& banned) {
  auto it = lower_bound(all(banned), u);
  int ans = 0;
  if (it != banned.end() and *it == u) {
    ans = -INF;
  }
  for (auto v : adj[u]) {
    if (v == p) continue;
    auto it = lower_bound(all(banned), v);
    bool ban = (it != banned.end() and *it == v);
    int child = 1 + dfs2(v, u, banned);
    if (child == 1 and ban) continue;
    ans = max(ans, child);
  }
  return ans;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
#ifdef LOCAL_PROJECT
#else
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
#endif
  int n, m, q;
  cin >> n >> m >> q;

  k = sqrt(n);

  for (int i = 0; i < m; ++i) {
    int s, e;
    cin >> s >> e;
    adj[e].pb(s);
  }

  for (int i = n; i >= 1; --i) {
    if (vis[i]) continue;
    dfs(i, 0);
  }

  while (q--) {
    int t, y;
    cin >> t >> y;
    vi v(y);
    for (int i = 0; i < y; ++i) cin >> v[i];

    if (false) {
      bool f = false;
      for (int i = 0; i < k; ++i) {
        if (towns[t][i].s == 0) break;
        auto pos = lower_bound(all(v), towns[t][i].s);
        if (pos != v.end() and *pos == towns[t][i].s) continue;
        cout << towns[t][i].f << endl;
        f = true;
        break;
      }

      if (!f) cout << -1 << endl;
    } else {
      int ans = dfs2(t, 0, v);
      if (ans < 0)
        cout << -1;
      else
        cout << ans;
      cout << endl;
    }
  }
}

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