Submission #1010255

#TimeUsernameProblemLanguageResultExecution timeMemory
1010255phongBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2028 ms146008 KiB
#include<bits/stdc++.h> #define ll long long const int nmax = 2e5 + 5, N = 3e5 + 5; const ll oo = 1e18; const int lg = 18, M = 4e3; const int base = 2e5, mod = 1e9 + 7; #define pii pair<int, int> #define fi first #define se second #define endl "\n" #define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';cout << endl using namespace std; vector<int> adj[nmax]; vector<pii> gg[nmax]; int n, m, q; int vis[nmax], c[nmax], dp[nmax]; int res[nmax], a[nmax]; main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); // freopen("code.inp", "r", stdin); // freopen("code.out", "w", stdout); cin >> n >> m >> q; for(int i = 1, u, v; i <= m; ++i){ cin >> u >> v; adj[v].push_back(u); } int S = 100; vector<pii> tmp; for(int i = 1; i <= n; ++i){ gg[i].push_back({0, i}); for(auto v : adj[i]){ for(auto [d, x] : gg[v]){ tmp.push_back({d + 1, x}); res[x] = max(res[x], d + 1); } } for(auto [d, x] : tmp){ if(res[x] == d){ gg[i].push_back({d, x}); res[x] = 0; } } sort(gg[i].begin(), gg[i].end(), [](pii a, pii b){ return a.fi > b.fi; }); while(gg[i].size() > S) gg[i].pop_back(); // for(auto [d, x] : gg[i]) cout << x << ' '; // cout << endl; } while(q--){ int t, y; cin >> t >> y; if(y >= S){ for(int i = 1, x; i <= y; ++i) cin >> x, c[x] = 1; for(int i = 1; i <= n; ++i) dp[i] = -n; dp[t] = 0; for(int i = t; i >= 1; --i){ for(auto v : adj[i]){ // cout << i << ' ' << v << endl; dp[v] = max(dp[v], dp[i] + 1); } } int ans = -1; for(int i = 1; i <= t; ++i){ if(c[i]) continue; // cout << i << ' ' << dp[i] << endl; ans = max(ans, dp[i]); } for(int i = 1; i <= n; ++i)c[i] =dp[i]= 0; cout << ans << endl; } else{ for(int i = 1,x; i <= y; ++i){ cin >> x, c[x] = 1; a[i] = x; } bool ok = 0; for(auto [d, x] : gg[t]){ if(c[x]) continue; cout << d << endl; ok = 1; break; } for(int i = 1; i <= y; ++i) c[a[i]] = 0; if(!ok) cout << -1 << endl; } } } /* */

Compilation message (stderr)

bitaro.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main(){
      | ^~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:50:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         while(gg[i].size() > S) gg[i].pop_back();
      |               ~~~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...