Submission #916711

#TimeUsernameProblemLanguageResultExecution timeMemory
916711ParsaGolestaniBitaro’s Party (JOI18_bitaro)C++14
0 / 100
120 ms8788 KiB
#include <bits/stdc++.h> using namespace std; const int N = 100'000; const int SQ = 316; const int INF = 1'000'000'000; int n, m, q, mark[N + 10], dis[N + 10]; pair<int, int> far[N + 10][SQ + 10]; vector<pair<int, int>> in[N + 10]; vector<int> out[N + 10]; void readInput() { cin >> n >> m >> q; for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; out[u].push_back(v); in[v].push_back({u, 0}); } } void calcFar() { for (int i = 1; i <= n; i++) { fill(far[i] + 1, far[i] + SQ + 1, make_pair(-INF, 0)); for (int j = 1; j <= SQ; j++) { pair<pair<int, int>, int> res = {{-INF, 0}, -1}; for (int x = 0; x < in[i].size(); x++) { int v = in[i][x].first, ind = in[i][x].second; while (ind < SQ && mark[far[v][ind + 1].second]) ind++; if (ind < SQ) res = max(res, make_pair(far[v][ind + 1], x)); } far[i][j] = res.first; far[i][j].first++; mark[far[i][j].second] = true; if (res.second != -1) in[i][res.second].second++; /*if (far[i][j].second) cout << i << ' ' << j << ": " << far[i][j].first << ' ' << far[i][j].second << '\n';*/ } for (int j = 1; j <= SQ; j++) if (far[i][j].first < 0) { far[i][j] = {0, i}; break; } for (int j = 1; j <= SQ; j++) mark[far[i][j].second] = false; } } void query() { int u, cnt; cin >> u >> cnt; vector<int> vec; for (int i = 1; i <= cnt; i++) { int v; cin >> v; vec.push_back(v); mark[v] = true; } if (cnt < SQ) { for (int i = 1; i <= SQ; i++) if (!mark[far[u][i].second]) { cout << (far[u][i].first < 0? -1: far[u][i].first) << '\n'; break; } } else { fill(dis + 1, dis + u + 1, -INF); dis[u] = 0; int ans = -1; for (int i = u - 1; i >= 1; i--) { for (auto v: out[i]) dis[i] = max(dis[i], dis[v] + 1); if (!mark[i]) ans = max(ans, dis[i]); } } for (auto x: vec) mark[x] = false; } void solve() { while (q--) query(); cout.flush(); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); readInput(); calcFar(); solve(); return 0; }

Compilation message (stderr)

bitaro.cpp: In function 'void calcFar()':
bitaro.cpp:28:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |             for (int x = 0; x < in[i].size(); x++) {
      |                             ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...