Submission #1359919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1359919		altern23	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	711 ms	419484 KiB

bitaro

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

#define ll long long

const int SQRT = 200;

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];
            vector <bool> vis(N+5);
            
            for (int i = 1; i <= N; i++) {
                  opt[i].push_back({0, i});
                  for (auto x : adj[i]) {
                        vector <pair<ll, ll>> nv;
                        ll L = 0, R = 0;
                        while (nv.size() < SQRT) {
                              while (L < opt[i].size() && vis[opt[i][L].second]) L++;
                              while (R < opt[x].size() && vis[opt[x][R].second]) R++;
                              if (L == opt[i].size() && R == opt[x].size()) break;
                              
                              if (L == opt[i].size()) {
                                    nv.push_back(opt[x][R++]);
                                    nv.back().first++;
                              }
                              else if (R == opt[x].size()) {
                                    nv.push_back(opt[i][L++]);
                              }
                              else {
                                    if (opt[i][L].first > opt[x][R].first+1) {
                                          nv.push_back(opt[i][L++]);
                                    }
                                    else {
                                          nv.push_back(opt[x][R++]);
                                          nv.back().first++;
                                    }
                              }
                              vis[nv.back().second] = 1;
                        }

                        for (auto [z, x] : nv) vis[x] = 0;

                        nv.swap(opt[i]);
                  }
            }

            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;
            }
      }
}

/*

*/

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