제출 #916715

#제출 시각아이디문제언어결과실행 시간메모리
916715ParsaGolestaniBitaro’s Party (JOI18_bitaro)C++14
0 / 100
6 ms8792 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(int u) { for (int j = 1; j <= SQ; j++) { far[u][j] = {-INF, 0}; for (int k = 0; k < in[u].size(); k++) { int v = in[u][k].first; while (in[u][k].second < SQ && mark[far[v][in[u][k].second + 1].second]) in[u][k].second++; if (in[u][k].second < SQ) far[u][j] = max(far[u][j], far[v][in[u][k].second + 1]); } far[u][j].first += (far[u][j].first == -INF? 0: 1); if (far[u][j].second) mark[far[u][j].second] = true; } for (int j = 1; j <= SQ; j++) if (far[u][j].first < 0) { far[u][j] = {0, u}; break; } for (int j = 1; j <= SQ; j++) mark[far[u][j].second] = false; } void calcFar() { for (int i = 1; i <= n; i++) calcFar(i); } 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 = (mark[u]? -1: 0); 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]); } cout << ans << '\n'; } 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; }

컴파일 시 표준 에러 (stderr) 메시지

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