#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,tes,t,i,j,zx,xc,T=300,k[100009],fx[100009],fr,sc,cnt;
int mx[100009];
bool bo[100009];
pair <int, int> dp[100009][302],tt[302];
vector <int> v[100009];
void dfsst(int q){
bo[q]=1;
dp[q][1].first=1;
dp[q][1].second=q;
for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
if(bo[(*it)]==0) dfsst((*it));
fr=1;sc=1;cnt=0;
while(1){
if(dp[q][fr].first==0&&dp[(*it)][sc].first==0) break;
if(cnt>T) break;
if(dp[q][fr].first>=dp[(*it)][sc].first+1){
cnt++;tt[cnt]=dp[q][fr];fr++;
}else{
cnt++;tt[cnt].first=dp[(*it)][sc].first+1;tt[cnt].second=dp[(*it)][sc].second;sc++;
}
}
for(j=1; j<=cnt; j++){
dp[q][j]=tt[j];
}
}
}
void dfs(int q){
if(fx[q]!=t) mx[q]=1;
for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
dfs((*it));
if(mx[q]<mx[(*it)]+1) mx[q]=mx[(*it)]+1;
}
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>b>>tes;
for(i=1; i<=b; i++){
cin>>c>>d;
if(c>d) swap(c,d);
v[d].push_back(c);
}
for(i=1; i<=a; i++){
if(bo[i]==1) continue;
dfsst(i);
}
for(t=1; t<=tes; t++){
cin>>c>>d;
for(i=1; i<=d; i++){
cin>>k[i];
fx[k[i]]=t;
}
if(d>=T){
for(i=1; i<=a; i++) mx[i]=0;
dfs(c);
if(mx[c]==0){
cout<<-1<<endl;
}else{
cout<<mx[c]-1<<endl;
}
}else{
for(i=1; ; i++){
if(fx[dp[c][i].second]!=t){
cout<<dp[c][i].first-1<<endl;
break;
}
}
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2680 KB |
Output is correct |
2 |
Correct |
6 ms |
2680 KB |
Output is correct |
3 |
Correct |
6 ms |
2680 KB |
Output is correct |
4 |
Correct |
6 ms |
2680 KB |
Output is correct |
5 |
Correct |
10 ms |
5240 KB |
Output is correct |
6 |
Correct |
10 ms |
5112 KB |
Output is correct |
7 |
Incorrect |
9 ms |
5112 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2680 KB |
Output is correct |
2 |
Correct |
6 ms |
2680 KB |
Output is correct |
3 |
Correct |
6 ms |
2680 KB |
Output is correct |
4 |
Correct |
6 ms |
2680 KB |
Output is correct |
5 |
Correct |
10 ms |
5240 KB |
Output is correct |
6 |
Correct |
10 ms |
5112 KB |
Output is correct |
7 |
Incorrect |
9 ms |
5112 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2680 KB |
Output is correct |
2 |
Correct |
6 ms |
2680 KB |
Output is correct |
3 |
Correct |
6 ms |
2680 KB |
Output is correct |
4 |
Correct |
6 ms |
2680 KB |
Output is correct |
5 |
Correct |
10 ms |
5240 KB |
Output is correct |
6 |
Correct |
10 ms |
5112 KB |
Output is correct |
7 |
Incorrect |
9 ms |
5112 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |