Submission #1262108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262108		thecyb	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	826 ms	143384 KiB

bitaro

/*
    ==                     ==
                 <^\()/^>               <^\()/^>
                  \/  \/                 \/  \/
                   /__\      .  '  .      /__\
      ==            /\    .     |     .    /\            ==
   <^\()/^>       !_\/       '  |  '       \/_!       <^\()/^>
    \/  \/     !_/I_||  .  '   \'/   '  .  ||_I\_!     \/  \/
     /__\     /I_/| ||      -==C++==-      || |\_I\     /__\
     /_ \   !//|  | ||  '  .   /.\   .  '  || |  |\\!   /_ \
    (-   ) /I/ |  | ||       .  |  .       || |  | \I\ (=   )
     \__/!//|  |  | ||    '     |     '    || |  |  |\\!\__/
     /  \I/ |  |  | ||       '  .  '    *  || |  |  | \I/  \
    {_ __}  |  |  | ||                     || |  |  |  {____}
 _!__|= ||  |  |  | ||   *      +          || |  |  |  ||  |__!_
 _I__|  ||__|__|__|_||          A          ||_|__|__|__||- |__I_
 -|--|- ||--|--|--|-||       __/_\__  *    ||-|--|--|--||= |--|-
  |  |  ||  |  |  | ||      /\-'o'-/\      || |  |  |  ||  |  |
  |  |= ||  |  |  | ||     _||:<_>:||_     || |  |  |  ||= |  |
  |  |- ||  |  |  | || *  /\_/=====\_/\  * || |  |  |  ||= |  |
  |  |- ||  |  |  | ||  __|:_:_[I]_:_:|__  || |  |  |  ||- |  |
 _|__|  ||__|__|__|_||:::::::::::::::::::::||_|__|__|__||  |__|_
 -|--|= ||--|--|--|-||:::::::::::::::::::::||-|--|--|--||- |--|-
  jgs|- ||  |  |  | ||:::::::::::::::::::::|| |  |  |  ||= |  |
~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^~~~~~~~~~
*/
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define ff first
#define ss second

void steroids() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
}

const int BLOCK_SIZE = 100;

int main() {
  steroids();
  int n, m, q;
  std::cin >> n >> m >> q;
  std::vector<std::vector<int>>radj(n);
  for (int i = 0; i < m; i++) {
    int u, v;
  std::cin >> u >> v;
  u--; v--;
  radj[v].push_back(u);
  }
  std::vector<std::vector<std::pair<int, int>>> longest(n);
  std::vector<int> dist(n, -1);
  for (int i = 0; i < n; i++) {
    longest[i].push_back({0, i});
    std::vector<int> reachable;
    for (const int &v : radj[i]) {
      for (const std::pair<int, int> &p : longest[v]) {
        if (dist[p.ss] == -1) {
          reachable.push_back(p.ss);
          dist[p.ss] = p.ff + 1;
        } else {
          dist[p.ss] = std::max(dist[p.ss], p.ff + 1);
        }
      }
    }
    for (const int &r : reachable) { longest[i].push_back({dist[r], r});}
    std::sort(longest[i].rbegin(), longest[i].rend());
    while (longest[i].size() > BLOCK_SIZE) { longest[i].pop_back();}
    for (const int &r : reachable) dist[r] = -1;
  }
  std::vector<bool> is_blocked(n);
  for (int i = 0; i < q; i++) {
    int t, y;
  std::cin >> t >> y;
  t--;
  std::vector<int> blocked_town(y);
  for (int j = 0; j < y; j++) {
    std::cin >> blocked_town[j];
  is_blocked[--blocked_town[j]] = true;
  }
  int ans = -1;
  if (y >= BLOCK_SIZE) {
    std::vector<int> dp(t+1, -1);
    dp[t] = 0;
    for (int i = t; i >= 0; i--) {
      if (dp[i] == -1) continue;
    if (!is_blocked[i]) { ans = std::max(ans, dp[i]);}
    for (const int &j : radj[i]) { dp[j] = std::max(dp[j], dp[i] + 1); }
    }
  } else {
    for (const std::pair<int, int> &p : longest[t]) {
      if (!is_blocked[p.ss]) {
        ans = p.ff;
        break;
      }
    }
  }
  std::cout << ans << '\n';
  for (const int &a : blocked_town) is_blocked[a] = false;
  }
}

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