제출 #560669

#제출 시각아이디문제언어결과실행 시간메모리
560669colossal_pepeBitaro’s Party (JOI18_bitaro)C++17
100 / 100
1625 ms411420 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; const int INF = 1e9; const int BLOCK_SZ = 450; int n, m, q; vector<vector<int>> g; vector<vector<pair<int, int>>> d; void precomp() { int dist_from[n] = {0}; for (int u = 0; u < n; u++) { vector<int> s; dist_from[u] = 0; s.push_back(u); for (int v : g[u]) { for (auto [x, y] : d[v]) { if (dist_from[y] >= x + 1) continue; if (dist_from[y] == 0) s.push_back(y); dist_from[y] = x + 1; } } sort(s.begin(), s.end(), [&dist_from](int i, int j) { return dist_from[i] < dist_from[j]; }); while (not s.empty()) { if (d[u].size() < BLOCK_SZ) d[u].push_back({dist_from[s.back()], s.back()}); dist_from[s.back()] = 0; s.pop_back(); } } } int getAns(int t, bool is_busy[]) { int i = 0; while (i < d[t].size() and is_busy[d[t][i].second]) i++; return (i < d[t].size() ? d[t][i].first : -1); } int comptueAns(int t, bool is_busy[]) { int dp[t + 1]; for (int u = 0; u <= t; u++) { dp[u] = -INF; for (int v : g[u]) { dp[u] = max(dp[u], dp[v] + 1); } if (not is_busy[u]) dp[u] = max(dp[u], 0); } return max(dp[t], -1); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> q; g.resize(n), d.resize(n); while (m--) { int u, v; cin >> u >> v; u--, v--; g[v].push_back(u); } precomp(); // for (int i = 0; i < n; i++) { // for (auto [x, y] : d[i]) { // cout << x << ' ' << y << " | "; // } // cout << '\n'; // } vector<int> busy_ppl; bool is_busy[n] = {0}; while (q--) { int t, y; cin >> t >> y; t--; busy_ppl.resize(y); for (int &c : busy_ppl) { cin >> c; c--; is_busy[c] = 1; } cout << (y < BLOCK_SZ ? getAns(t, is_busy) : comptueAns(t, is_busy)) << '\n'; for (int &c : busy_ppl) { is_busy[c] = 0; } busy_ppl.clear(); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

bitaro.cpp: In function 'int getAns(int, bool*)':
bitaro.cpp:39:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     while (i < d[t].size() and is_busy[d[t][i].second]) i++;
      |            ~~^~~~~~~~~~~~~
bitaro.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     return (i < d[t].size() ? d[t][i].first : -1);
      |             ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...