제출 #1359907

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1359907		altern23	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	1445 ms	589824 KiB

bitaro

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

#define ll long long

const int SQRT = 350;

int main() {
      ios_base::sync_with_stdio(0); cin.tie(0);
      int tc = 1;
      // cin >> tc;
      while (tc--) {
            ll N, M, Q; cin >> N >> M >> Q;

            vector <ll> adj[N+5], jda[N+5];

            for (int i = 1; i <= M; i++) {
                  ll u, v; cin >> u >> v;
                  adj[v].push_back(u);
                  jda[u].push_back(v);
            }

            vector <pair<ll, ll>> opt[N+5];

            for (int i = 1; i <= N; i++) {
                  opt[i].push_back({0, i});
                  for (auto x : adj[i]) {
                        for (auto j : opt[x]) opt[i].push_back({j.first+1, j.second});
                        sort(opt[i].rbegin(), opt[i].rend());
                        while (opt[i].size() > SQRT) opt[i].pop_back();
                  }
            }

            vector <bool> busy(N+5);

            for (int i = 1; i <= Q; i++) {
                  ll T, Y; cin >> T >> Y;
                  vector <ll> cur;
                  for (int j = 1; j <= Y; j++) {
                        ll x; cin >> x;
                        cur.push_back(x);
                        busy[x] = 1;
                  }

                  ll ans = -1;

                  if (cur.size() < SQRT) {
                        for (auto [z, x] : opt[T]) {
                              if (!busy[x]) {
                                    ans = z;
                                    break;
                              }
                        }
                  }
                  else {
                        vector <ll> dp(N+5, -1e9);
                        for (int j = T; j >= 1; --j) {
                              if (j == T) dp[T] = 0;
                              else {
                                    for (auto x : jda[j]) {
                                          dp[j] = max(dp[j], dp[x]+1);
                                    }
                              }
                              if (!busy[j]) ans = max(ans, dp[j]);
                        }
                  }

                  cout << ans << "\n";

                  for (auto x : cur) busy[x] = 0;
            }
      }
}

/*

*/

• 서브태스크 1: 7 / 7
• 서브태스크 2: 0 / 7
• 서브태스크 3: 0 / 86