Submission #521212

#TimeUsernameProblemLanguageResultExecution timeMemory
521212JomnoiBitaro’s Party (JOI18_bitaro)C++17
100 / 100
1504 ms419632 KiB
#include <bits/stdc++.h> #define DEBUG 0 using namespace std; const int N = 1e5 + 10; const int M = 300; const int INF = 1e9 + 7; vector <int> rev[N]; vector <pair <int, int>> node[N]; stack <int> tmp; bool notuse[N]; int dp[N]; int sz[N]; int solve(int u) { if(dp[u] != -1) { return dp[u]; } dp[u] = -INF; for(auto v : rev[u]) { int x = solve(v); if(x != -INF) { dp[u] = max(dp[u], solve(v) + 1); } } if(notuse[u] == false) { dp[u] = max(dp[u], 0); } return dp[u]; } int main() { cin.tie(0)->sync_with_stdio(0); int n, m, q; cin >> n >> m >> q; while(m--) { int s, e; cin >> s >> e; rev[e].push_back(s); } for(int u = 1; u <= n; u++) { for(auto v : rev[u]) { sz[v] = 0; } for(int i = 1; i <= M; i++) { pair <int, int> best = make_pair(-1, u); int idx = -1; for(auto v : rev[u]) { while(sz[v] < node[v].size() and notuse[node[v][sz[v]].second] == true) { sz[v]++; } if(sz[v] < node[v].size() and best.first < node[v][sz[v]].first) { best = node[v][sz[v]]; idx = v; } } node[u].emplace_back(best.first + 1, best.second); if(best.second == u) { break; } tmp.push(best.second); notuse[best.second] = true; } while(!tmp.empty()) { notuse[tmp.top()] = false; tmp.pop(); } } if(DEBUG) { for(int i = 1; i <= n; i++) { for(auto [v, c] : node[i]) { cout << i << " : " << v << " " << c << endl; } cout << endl; } } while(q--) { int t, y; cin >> t >> y; int k = y; while(y--) { int c; cin >> c; notuse[c] = true; tmp.push(c); } int ans = -INF; if(k < M) { for(auto [v, c] : node[t]) { if(notuse[c] == false) { ans = v; break; } } } else { for(int i = 1; i <= t; i++) { dp[i] = -1; } ans = solve(t); } if(ans == -INF) { ans = -1; } cout << ans << '\n'; while(!tmp.empty()) { notuse[tmp.top()] = false; tmp.pop(); } } return 0; }

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:54:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |                 while(sz[v] < node[v].size() and notuse[node[v][sz[v]].second] == true) {
      |                       ~~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:57:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                 if(sz[v] < node[v].size() and best.first < node[v][sz[v]].first) {
      |                    ~~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:52:17: warning: variable 'idx' set but not used [-Wunused-but-set-variable]
   52 |             int idx = -1;
      |                 ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...