제출 #465850

#제출 시각아이디문제언어결과실행 시간메모리
465850jli12345Bitaro’s Party (JOI18_bitaro)C++14
7 / 100
2109 ms410988 KiB
#include <bits/stdc++.h> using namespace std; void fastIO(){ ios_base::sync_with_stdio(false); cin.tie(0); } const int SQRT = 316; vector<int> arr[100100]; vector<pair<int, int> > far[100100]; int dist[100100]; int vis[100100]; bool cmp(int a, int b){ return dist[a] > dist[b]; } int main(){ fastIO(); int N, M, Q; cin >> N >> M >> Q; for (int i = 1; i <= M; i++){ int a, b; cin >> a >> b; arr[b].push_back(a); } for (int i = 1; i <= N; i++){ vector<int> all; for (int j = 0; j < (int)arr[i].size(); j ++){ int x = arr[i][j]; for (int k = 0; k < far[x].size(); k ++){ int z = far[x][k].second; if (vis[z] != i){ vis[z] = i; all.push_back(z); dist[z] = far[x][k].first + 1; } else{ dist[z] = max(dist[z], far[x][k].first + 1); } } if (vis[x] != i){ vis[x] = i; all.push_back(x); dist[x] = 1; } } all.push_back(i); sort(all.begin(), all.end(), cmp); for (int j = 0; j < min((int)all.size(), SQRT); j ++){ far[i].push_back(make_pair(dist[all[j]], all[j])); } } /* for (int i = 1; i <= N; i++){ vector<int> all; all.push_back(i); dist[i] = 0; vis[i] = i; for (int j = 0; j < (int)arr[i].size(); j++){ int nx = arr[i][j]; if (vis[nx] != i){ all.push_back(nx); dist[nx] = 1; vis[nx] = i; } for (int k = 0; k < (int)far[nx].size(); k++){ if (vis[far[nx][k].second] != i){ dist[far[nx][k].second] = far[nx][k].first+1; all.push_back(far[nx][k].second); vis[far[nx][k].second] = i; } else { dist[far[nx][k].second] = max(dist[far[nx][k].second], far[nx][k].first+1); } } } sort(all.begin(), all.end(), cmp); for (int j = 0; j < min((int)all.size(), SQRT); j++){ far[i].push_back({dist[all[j]], all[j]}); } sort(far[i].begin(), far[i].end(), greater<pair<int, int> >()); }*/ memset(vis, 0, sizeof(vis)); for (int i = 1; i <= Q; i++){ int T, R; cin >> T >> R; for (int j = 1; j <= R; j++){ int y; cin >> y; vis[y] = i; } /* if (R < SQRT){ bool work = false; for (int j = 0; j < (int)far[T].size(); j++){ int nx = far[T][j].second; if (vis[nx] != i){ cout << far[T][j].first << "\n"; work = true; break; } } if (!work) cout << -1 << "\n"; } else { memset(dist, -1, sizeof(dist)); dist[T] = 0; for (int j = T; j >= 1; j--){ for (int nx : arr[j]){ dist[nx] = max(dist[nx], dist[j]+1); } } int mx = -1; for (int j = T; j >= 1; j--){ if (vis[j] == i) continue; mx = max(mx, dist[j]); } cout << mx << "\n"; }*/ if (R >= SQRT){ vector<int> dp(N+1, -1); for (int j = 1; j <= T; j ++){ if (vis[j] != i){ dp[j] = max(dp[j], 0); } for (int k = 0; k < (int)arr[j].size(); k ++){ if (dp[arr[j][k]] != -1) dp[j] = max(dp[j], dp[arr[j][k]] + 1); } } cout << dp[T] << '\n'; } else{ for (int j = 0; j < (int)far[T].size(); j ++){ if (vis[far[T][j].second] != i){ cout << far[T][j].first << '\n'; goto done; } } cout << -1 << '\n'; done: continue; } } }

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

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