Submission #863846

#TimeUsernameProblemLanguageResultExecution timeMemory
863846biximoBitaro’s Party (JOI18_bitaro)C++17
7 / 100
979 ms524288 KiB
#include <bits/stdc++.h> #define N 100005 #define BL 70 using namespace std; typedef pair<int, int> pi; int n, m, q; vector<int> paths[N], NOT; vector<pi> dp[N]; bool added[N]; void dfs() { for(auto&i: added) i = 0; for(int cur = 1; cur <= n; cur ++) { for(int i: paths[cur]) { int a = 0, b = 0; vector<pi> temp; temp.reserve(BL); while(temp.size() < BL && a < dp[cur].size() || b < dp[i].size()) { if(a == dp[cur].size() || (b < dp[i].size() && dp[cur][a].first + 1 < dp[i][b].first)) { if(!added[dp[i][b].second]) temp.push_back(dp[i][b]); added[dp[i][b].second] = 1; b ++; } else { if(!added[dp[cur][a].second]) temp.push_back({dp[cur][a].first + 1, dp[cur][a].second}); added[dp[cur][a].second] = 1; a ++; } } for(int j = 0; j < a; j ++) added[dp[cur][j].second] = 0; for(int j = 0; j < b; j ++) added[dp[i][j].second] = 0; swap(temp, dp[i]); } } } int ANS[N]; bool allowed[N] = {0}; void DP() { for(int cur = 1; cur <= n; cur ++) { if(ANS[cur] == -1) continue; for(int i: paths[cur]) { ANS[i] = max(ANS[i], ANS[cur] + 1); } } } int main() { cin.tie(0)->sync_with_stdio(0); for(auto&i: allowed) i = 1; cin >> n >> m >> q; for(int i = 1; i <= n; i ++) { allowed[i] = 1; dp[i].reserve(BL); dp[i].push_back({0, i}); } while(m--) { int a, b; cin >> a >> b; paths[a].push_back(b); } dfs(); while(q--) { int a, b; cin >> a >> b; NOT.resize(b); for(auto&i: NOT) { cin >> i; allowed[i] = 0; } if(b > BL) { for(auto&i: ANS) i = 0; for(auto i: NOT) ANS[i] = -1; DP(); cout << ANS[a] << "\n"; } else { bool adde = true; for(auto&[v, i]: dp[a]) { if(allowed[i]) { adde = false; cout << (v) << "\n"; break; } } if(adde) cout << -1 << "\n"; } for(auto&i: NOT) allowed[i] = 1; } }

Compilation message (stderr)

bitaro.cpp: In function 'void dfs()':
bitaro.cpp:17:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |             while(temp.size() < BL && a < dp[cur].size() || b < dp[i].size()) {
      |                                       ~~^~~~~~~~~~~~~~~~
bitaro.cpp:17:63: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |             while(temp.size() < BL && a < dp[cur].size() || b < dp[i].size()) {
      |                                                             ~~^~~~~~~~~~~~~~
bitaro.cpp:17:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   17 |             while(temp.size() < BL && a < dp[cur].size() || b < dp[i].size()) {
      |                   ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:18:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |                 if(a == dp[cur].size() || (b < dp[i].size() && dp[cur][a].first + 1 < dp[i][b].first)) {
      |                    ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:18:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |                 if(a == dp[cur].size() || (b < dp[i].size() && dp[cur][a].first + 1 < dp[i][b].first)) {
      |                                            ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...