Submission #790440

#	Time	Username	Problem	Language	Result	Execution time	Memory
790440		anton	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1220 ms	211508 KiB

bitaro

    #include <bits/stdc++.h>
    using namespace std;
     
    const int MAX_N = 1e5 + 5;
    const int K = 150;
    vector<int> G[MAX_N];
    vector<pair<int, int>> values[MAX_N];
    int max_value[MAX_N], dp[MAX_N] = {};
    bool vis[MAX_N] = {}, used[MAX_N] = {};
    vector<int> order;
     
    void topsort(int u) {
      vis[u] = true;
      for (int v : G[u]) {
        if (!vis[v]) {
          topsort(v);
        }
      }
      order.push_back(u);
    }
     
    void DFS(int u) {
      vis[u] = true;
      for (int v : G[u]) {
        if (!vis[v]) {
          DFS(v);
        }
      }
    }
     
    int main() {
      cin.tie(nullptr)->sync_with_stdio(false);
      int N, M, Q;
      cin >> N >> M >> Q;
      for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        G[v].push_back(u);
      }
      order.reserve(N);
      for (int i = 0; i < N; i++) {
        if (!vis[i]) {
          topsort(i);
        }
      }
      memset(max_value, -1, sizeof max_value);
      for (int i : order) {
        values[i] = {{0, i}};
        for (int j : G[i]) {
          vector<int> vals;
          for (auto [val, v] : values[i]) {
            vals.push_back(v);
            max_value[v] = -val;
          }
          for (auto [val, v] : values[j]) {
            if (max_value[v] == -1) {
              vals.push_back(v);
            }
            max_value[v] = max(max_value[v], -val + 1);
          }
          values[i] = vector<pair<int, int>>();
          for (int p : vals) {
            values[i].push_back({-max_value[p], p});
          }
          if (values[i].size() > K) {
            nth_element(values[i].begin(), values[i].begin() + K, values[i].end());
            values[i].resize(K);
          }
          for (int p : vals) {
            max_value[p] = -1;
          }
        }
      } 
      for (int q = 0; q < Q; q++) {
        int T, Y;
        cin >> T >> Y;
        T--;
        vector<int> C(Y);
        for (int &v : C) {
          cin >> v;
          used[--v] = true;
        }
        if (Y < K) {
          int ans = -1;
          for (auto [val, v] : values[T]) {
            ans = -val > ans && !used[v] ? -val : ans;
          }
          cout << ans << "\n";
        } else {
          memset(dp, -1, sizeof dp);
          for (int i : order) {
            if (!used[i]) {
              dp[i] = 0;   
            }
            for (int j : G[i]) {
              if (dp[j] != -1) {
                dp[i] = dp[j] + 1 > dp[i] ? dp[j] + 1 : dp[i]; 
              }
            }
          }
          cout << dp[T] << "\n";
        }
        for (int v : C) {
          used[v] = false;
        }
      }
    }

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