Submission #1011629

#TimeUsernameProblemLanguageResultExecution timeMemory
1011629eysbutnoBitaro’s Party (JOI18_bitaro)C++17
7 / 100
1211 ms524288 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = array<int, 2>; #define all(x) begin(x), end(x) #define sz(x) (int) (x).size() template<class T> bool smax(T &a, T b) { return a < b ? a = b, 1 : 0; } template<class T> bool smin(T &a, T b) { return a > b ? a = b, 1 : 0; } #define int long long // wtf is wronggggg void solve() { int n, m, q; cin >> n >> m >> q; vector<vector<int>> adj(n); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adj[--v].push_back(--u); } const int B = (int) sqrt(n); // this code is sketch! vector<vector<pii>> best(n); for (int i = 0; i < n; i++) { best[i].push_back({i, 0}); for (int j : adj[i]) { for (auto [idx, len] : best[j]) { best[i].push_back({idx, len + 1}); } } sort(all(best[i]), [](auto &x, auto &y) -> bool { return x[1] > y[1]; }); best[i].erase(unique(all(best[i])), end(best[i])); while (sz(best[i]) > B) { best[i].pop_back(); } } // end vector<bool> ok(n, true); while (q--) { int t, y; cin >> t >> y; vector<int> c(y); for (int i = 0; i < y; i++) { cin >> c[i], ok[--c[i]] = false; } --t; int res = -1; if (y >= B) { vector<int> dp(t + 1, -1); dp[t] = 0; for (int i = t; i >= 0; i--) { if (dp[i] == -1) { continue; } if (ok[i]) { smax(res, dp[i]); } for (int j : adj[i]) { smax(dp[j], dp[i] + 1); } } } else { for (auto [idx, len] : best[t]) { if (ok[idx]) { res = len; break; } } } for (int i : c) { ok[i] = true; } cout << res << "\n"; } } signed main() { cin.tie(0) -> sync_with_stdio(0); int t = 1; // cin >> t; while (t--) solve(); }

Compilation message (stderr)

bitaro.cpp: In function 'void solve()':
bitaro.cpp:28:28: warning: narrowing conversion of 'i' from 'long long int' to 'int' [-Wnarrowing]
   28 |         best[i].push_back({i, 0});
      |                            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...