Submission #233428

#TimeUsernameProblemLanguageResultExecution timeMemory
233428DS007Bitaro’s Party (JOI18_bitaro)C++14
0 / 100
14 ms5760 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5; int n, m, q; vector<int> adj[N]; vector<pair<int, int>> far[N]; void pre() { for (int i = 0; i < n; i++) { priority_queue<pair<int, int>> pq; for (int j : adj[i]) { for (auto k : far[j]) pq.push(k); } unordered_set<int> s; for (int j = 0; j <= ceil(sqrt(n)) && !pq.empty();) { auto temp = pq.top(); pq.pop(); if (!s.count(temp.second)) { far[i].emplace_back(temp.first + 1, temp.second); s.insert(temp.second); j++; } } if (far[i].size() <= ceil(sqrt(n))) far[i].emplace_back(0, i); } } int calc(int t, const set<int>& c) { int dp[n] = {}; fill(dp, dp + n, -1); dp[t] = 0; for (int i = t; i >= 0; i--) { for (int j : adj[i]) dp[j] = max(dp[j], dp[i] + 1); } int ans = -1; for (int i = t; i >= 0; i--) { if (!c.count(i)) ans = max(ans, dp[i]); } return ans; } int find(int t, const set<int>& c) { for (auto i : far[t]) { if (!c.count(i.second)) return i.first; } return -1; } int solveTestCase(int test) { cin >> n >> m >> q; for (int i = 0; i < m; i++) { int s = 0, e = 0; cin >> s >> e; s--, e--; adj[e].push_back(s); } pre(); for (int i = 0; i < q; i++) { int t = 0, y = 0; cin >> t >> y; set<int> c; for (int j = 0; j < y; j++) { int temp = 0; cin >> temp; c.insert(temp - 1); } if (y >= floor(sqrt(n))) cout << calc(t - 1, c) << "\n"; else cout << find(t - 1, c) << "\n"; } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int test = 1; //cin >> test; for (int i = 1; i <= test; i++) solveTestCase(i); }

Compilation message (stderr)

bitaro.cpp: In function 'long long int solveTestCase(long long int)':
bitaro.cpp:89:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...