Submission #1261965

#TimeUsernameProblemLanguageResultExecution timeMemory
1261965tminhBitaro’s Party (JOI18_bitaro)C++20
0 / 100
5 ms5448 KiB
#include "bits/stdc++.h" using namespace std; #define task "" #define ll long long #define endl '\n' #define fi first #define se second #define vall(a) (a).begin(), (a).end() #define sze(a) (int)a.size() #define pii pair<int, int> #define pll pair<ll, ll> #define ep emplace_back #define pb push_back #define pf push_front const ll mod = 1e9 + 7; const int N = 1e5 + 5; const ll oo = 1e18; const int base = 320; bool START; int n, m, d[N], q, a[N]; vector<int> adj[N]; vector<pii> ds[N]; bool vis[N], del[N]; int get(int u) { for (int i = 1; i <= n; ++i) { vis[i] = false; d[i] = 0; if (del[i]) d[i] = -1; } for (int v = 1; v <= u; ++v) { for (int p : adj[v]) if (!del[p]) { d[v] = max(d[v], d[p] + 1); vis[v] = true; } } if (vis[u]) return d[u]; return -1; } inline void solve() { for (int u = 1; u <= n; ++u) { vector<int> tmp; for (int p : adj[u]) { for (auto [len, p_] : ds[p]) { if (!vis[p_]) { d[p_] = len + 1; tmp.pb(p_); vis[p_] = true; } else d[p_] = max(d[p_], len + 1); } } for (int p : tmp) { vis[p] = false; ds[u].pb(make_pair(d[p], p)); } ds[u].pb(make_pair(0, u)); sort(vall(ds[u]), greater<pii>()); while(sze(ds[u]) > base + 1) ds[u].pop_back(); } while(q--) { int u, x; cin >> u >> x; for (int i = 1; i <= x; ++i) { cin >> a[i]; del[a[i]] = true; } int ans = -1; if (x > base) { ans = get(u); } else { for (auto[len, p] : ds[u]) if (!del[p]) ans = max(ans, len); } cout << ans << endl; for (int i = 1; i <= x; ++i) del[a[i]] = false; } } inline void input() { cin >> n >> m >> q; for(int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; adj[v].pb(u); } return solve(); } bool END; int main() { if(fopen(task ".inp", "r")) { freopen(task ".inp", "r", stdin); freopen(task ".out", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); input(); cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << 's' << endl; cerr << "Memory: " << fabs ((&END - &START)) / 1048576.0 << "MB\n"; return 0; }

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...