Submission #735692

#TimeUsernameProblemLanguageResultExecution timeMemory
735692Mister_HDSBitaro’s Party (JOI18_bitaro)C++14
14 / 100
2066 ms155628 KiB
#include <bits/stdc++.h> #define ll long long #define endl "\n" #define IOS \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); using namespace std; const ll MOD = 1e9 + 7; const double EPS = 1e-7; const int MAX = (int)1e5 + 10; const double PI = acos(-1); vector<int> adj[MAX]; vector<int> par[MAX]; vector<pair<int, int>> shits[MAX]; int frq[MAX]; bool removed[MAX]; int sqrt_n = 115; void build(queue<int> q, vector<int> ind) { while (!q.empty()) { int curNode = q.front(); q.pop(); for (auto node : adj[curNode]) { ind[node]--; if (ind[node] == 0) q.push(node); } vector<pair<int, int>> &res = shits[curNode]; res.push_back({0, curNode}); for (auto node : par[curNode]) { for (auto x : shits[node]) // distance, node { frq[x.second] = max(frq[x.second], x.first + 1); } } for (auto node : par[curNode]) { for (auto x : shits[node]) { if (frq[x.second] > 0) { res.push_back({frq[x.second], x.second}); frq[x.second] = 0; } } } sort(res.rbegin(), res.rend()); while ((int)res.size() > sqrt_n+1) { res.pop_back(); } // cout << curNode << endl; // for(auto x : res) cout << x.first << " " << x.second << endl ; } } int bfs(queue<int> q, vector<int> ind, int n, int nodeParty) { vector<int> dis(n + 1, 0); while (!q.empty()) { int curNode = q.front(); q.pop(); for (auto node : adj[curNode]) { ind[node]--; if (ind[node] == 0) q.push(node); if (dis[curNode] == 0 && removed[curNode] == true) continue; dis[node] = max(dis[node], dis[curNode] + 1); } } return dis[nodeParty]; } void solve() { int n, m, q; scanf("%d%d%d" , &n , &m , &q) ; vector<int> ind(n + 1, 0); for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v) ; adj[u].push_back(v); par[v].push_back(u); ind[v]++; } queue<int> roots; for (int i = 1; i <= n; i++) { if (ind[i] == 0) roots.push(i); } build(roots, ind); while (q--) { int nodeParty, totalRemoved; vector<int> rmv; scanf("%d%d", &nodeParty, &totalRemoved) ; for (int i = 1; i <= totalRemoved; i++) { int node; scanf("%d", &node) ; rmv.push_back(node); } for (auto node : rmv) removed[node] = true; int sz = (int)rmv.size(); int ans = -1; if (sz >= sqrt_n) { // FIRST TYPE OF QUESRIES ans = bfs(roots, ind, n, nodeParty); } else { for (auto node : shits[nodeParty]) { if (removed[node.second] == false) { ans = max(ans, node.first); } } } if (ans == 0 && removed[nodeParty] == true) ans = -1; printf("%d\n", ans) ; for (auto node : rmv) removed[node] = false; } } int main() { //IOS; solve(); return 0; }

Compilation message (stderr)

bitaro.cpp: In function 'void solve()':
bitaro.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |  scanf("%d%d%d" , &n , &m , &q) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |   scanf("%d%d", &u, &v) ;
      |   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |   scanf("%d%d", &nodeParty, &totalRemoved) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:117:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |    scanf("%d", &node) ;
      |    ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...