제출 #465847

#제출 시각아이디문제언어결과실행 시간메모리
465847jli12345Bitaro’s Party (JOI18_bitaro)C++14
0 / 100
8 ms6220 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; 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]; 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"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...