이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
vector<pii> best[100003];
vector<int> rev[100003];
bool toff[100003];
int vis[100003];
int dp[100003];
const int siz=300;
int dfs(int v){
dp[v]=0;
int ans=-1;
for (auto u : rev[v]){
ans=max(ans,dfs(u));
dp[v]=max(dp[v],dp[u]+1);
}
return toff[v]?ans:max(dp[v],ans);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m,q;
cin >> n >> m >> q;
for (int i = 1,s,t; i<=m; i++){
cin >> s >> t;
rev[t].push_back(s);
}
priority_queue<pii> pq;
for (int i = 1; i<=n; i++){
pq.push({0,i});
for (auto u : rev[i]){
for (auto [v,d] : best[u]){
pq.push({d+1,v});
}
}
for (;best[i].size()<siz && pq.size();pq.pop()){
auto [d,v] = pq.top();
if (vis[v]!=i){
vis[v]=i;
best[i].push_back({v,d});
}
}
for(;pq.size();pq.pop());
}
vector<int> wej;
for (int i = 1, fin, num; i<=q; i++){
cin >> fin >> num;
for (int j = 1, v; j<=num; j++){
cin >> v;
wej.push_back(v);
}
for (auto u : wej)toff[u]=true;
if (num>=siz)cout << dfs(fin) << '\n';
else{
int ans=-1;
for (auto [u,d] : best[fin]){
if (!toff[u])ans=max(ans,d);
}
cout << ans << '\n';
}
for (auto u : wej)toff[u]=false;
wej.clear();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |