Submission #1031201

#TimeUsernameProblemLanguageResultExecution timeMemory
1031201belgianbotBitaro’s Party (JOI18_bitaro)C++14
14 / 100
122 ms22864 KiB
#include <bits/stdc++.h> using namespace std; int N, M, Q; vector<vector<int>> adj, revAdj; vector<int> memo; int goal; int dp(int pos) { if (pos > goal) return INT_MIN; if (pos == goal) return 0; if (memo[pos] != -1) return memo[pos]; int ans = INT_MIN; for (int x : adj[pos]) { ans = max(ans, dp(x) + 1); } return memo[pos] = ans; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> N >> M >> Q; adj.resize(N); revAdj.resize(N); for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; a--; b--; adj[a].push_back(b); revAdj[b].push_back(a); } vector<vector<int>> busy(Q); vector<bool> dec(Q, false); vector<int> T(Q); for (int i = 0; i < Q; i++) { cin >> T[i]; T[i]--; int Y; cin >> Y; for (int j = 0; j < Y; j++) { int a; cin >> a; a--; busy[i].push_back(a); } if (Y < sqrt(N) - 230) dec[i] = true; } vector<vector<pair<int,int>>> sol(N); for (int i = 0; i < N; i++) { vector<int> it(int(revAdj[i].size()), 0); for (int k = 0; k < sqrt(N) - 230; k++) { pair<int,int> best = {INT_MAX, -1}; int index = -1; for (int j = 0; j < int(revAdj[i].size()); j++) { if (it[j] < sol[j].size() && sol[j][it[j]] < best) { best = sol[j][it[j]]; best.first--; index = j; } } if (index != -1) { it[index]++; sol[i].push_back(best); } } sol[i].push_back({0,i}); } for (int i = 0; i < Q; i++) { if (!dec[i]) { goal = T[i]; memo.clear(); memo.resize(T[i], -1); int ans = -1; for (int j = 0; j <= goal; j++) { auto it = lower_bound(busy[i].begin(), busy[i].end(), j); if (it == busy[i].end() || (*it) != j) ans = max(ans, dp(j)); } cout << ans << '\n'; } else { bool ok = false; for (auto x : sol[T[i]]) { auto it = lower_bound(busy[i].begin(), busy[i].end(), x.second); if (it == busy[i].end() || (*it) != x.second) { ok = true; cout << -x.first << '\n'; break; } } if (!ok) cout << -1 << '\n'; } } return 0; }

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:55:16: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |      if (it[j] < sol[j].size() && sol[j][it[j]] < best) {
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...