이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
void fastIO(){
ios_base::sync_with_stdio(false);
cin.tie(0);
}
const int SQRT = 80;
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];
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]});
}
}
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';*/
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{
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;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |