#include <bits/stdc++.h>
#define D 3003
#define maxN 100005
using namespace std;
vector <int> adj[maxN],u;
vector <pair<int,int>> d[maxN];
bool mar[maxN];
int n,m,q,i,j,x,y,t,ans;
vector<pair<int,int>> izbaci(vector<pair<int,int>> v){
vector<pair<int,int>> u;
int i;
for(i=0;i<v.size();i++){
if(!mar[v[i].second]){u.push_back(v[i]); mar[v[i].second]=true;}
}
for(i=0;i<u.size();i++) mar[u[i].second]=false;
while(u.size()>=D) u.pop_back();
return u;
}
vector<pair<int,int>> dodaj(vector <pair<int,int>> a,vector <pair<int,int>> b){
vector<pair<int,int>> v;
int i,j;
i=j=0;
while(i<a.size() && j<b.size()){
if(a[i].first>=b[j].first+1) {v.push_back(a[i]); i++;}
else {v.push_back({b[j].first+1,b[j].second}); j++;}
}
while(i<a.size()){
v.push_back(a[i]); i++;
}
while(j<b.size()){
v.push_back({b[j].first+1,b[j].second}); j++;
}
v=izbaci(v);
return v;
}
int resi(int x){
int ans=-1,tmp;
if(!mar[x]) ans=0;
for(int i=0;i<adj[x].size();i++){
tmp=resi(adj[x][i]);
if(tmp!=-1) ans=max(ans,tmp+1);
}
return ans;
}
int main()
{
srand(time(NULL));
std::ios_base::sync_with_stdio(0);
cin>>n>>m>>q;
for(i=0;i<m;i++){
cin>>x>>y;
adj[y].push_back(x);
}
for(i=1;i<=n;i++){
d[i].push_back({0,i});
for(j=0;j<adj[i].size();j++){
d[i]=dodaj(d[i],d[adj[i][j]]);
}
}
while(q--){
cin>>t>>x;
u.clear();
for(i=0;i<x;i++){
cin>>y;
mar[y]=true;
u.push_back(y);
}
if(x<D-2){
ans=-1;
for(i=0;i<d[t].size();i++){
if(!mar[d[t][i].second]){
ans=d[t][i].first;
break;
}
}
}
else{
ans=resi(t);
}
for(i=0;i<u.size();i++) mar[u[i]]=false;
cout<<ans<<endl;
}
return 0;
}
Compilation message
bitaro.cpp: In function 'std::vector<std::pair<int, int> > izbaci(std::vector<std::pair<int, int> >)':
bitaro.cpp:15:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v.size();i++){
~^~~~~~~~~
bitaro.cpp:18:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<u.size();i++) mar[u[i].second]=false;
~^~~~~~~~~
bitaro.cpp: In function 'std::vector<std::pair<int, int> > dodaj(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:27:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i<a.size() && j<b.size()){
~^~~~~~~~~
bitaro.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i<a.size() && j<b.size()){
~^~~~~~~~~
bitaro.cpp:31:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i<a.size()){
~^~~~~~~~~
bitaro.cpp:34:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j<b.size()){
~^~~~~~~~~
bitaro.cpp: In function 'int resi(int)':
bitaro.cpp:44:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[x].size();i++){
~^~~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<adj[i].size();j++){
~^~~~~~~~~~~~~~
bitaro.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<d[t].size();i++){
~^~~~~~~~~~~~
bitaro.cpp:86:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<u.size();i++) mar[u[i]]=false;
~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
11 ms |
5504 KB |
Output is correct |
6 |
Correct |
12 ms |
5504 KB |
Output is correct |
7 |
Correct |
11 ms |
5504 KB |
Output is correct |
8 |
Correct |
31 ms |
10624 KB |
Output is correct |
9 |
Correct |
35 ms |
10880 KB |
Output is correct |
10 |
Correct |
30 ms |
10488 KB |
Output is correct |
11 |
Correct |
24 ms |
8824 KB |
Output is correct |
12 |
Correct |
16 ms |
6528 KB |
Output is correct |
13 |
Correct |
34 ms |
8612 KB |
Output is correct |
14 |
Correct |
41 ms |
8440 KB |
Output is correct |
15 |
Correct |
23 ms |
6444 KB |
Output is correct |
16 |
Correct |
39 ms |
8440 KB |
Output is correct |
17 |
Correct |
27 ms |
8440 KB |
Output is correct |
18 |
Correct |
16 ms |
6528 KB |
Output is correct |
19 |
Correct |
26 ms |
8448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
11 ms |
5504 KB |
Output is correct |
6 |
Correct |
12 ms |
5504 KB |
Output is correct |
7 |
Correct |
11 ms |
5504 KB |
Output is correct |
8 |
Correct |
31 ms |
10624 KB |
Output is correct |
9 |
Correct |
35 ms |
10880 KB |
Output is correct |
10 |
Correct |
30 ms |
10488 KB |
Output is correct |
11 |
Correct |
24 ms |
8824 KB |
Output is correct |
12 |
Correct |
16 ms |
6528 KB |
Output is correct |
13 |
Correct |
34 ms |
8612 KB |
Output is correct |
14 |
Correct |
41 ms |
8440 KB |
Output is correct |
15 |
Correct |
23 ms |
6444 KB |
Output is correct |
16 |
Correct |
39 ms |
8440 KB |
Output is correct |
17 |
Correct |
27 ms |
8440 KB |
Output is correct |
18 |
Correct |
16 ms |
6528 KB |
Output is correct |
19 |
Correct |
26 ms |
8448 KB |
Output is correct |
20 |
Execution timed out |
2044 ms |
12024 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
11 ms |
5504 KB |
Output is correct |
6 |
Correct |
12 ms |
5504 KB |
Output is correct |
7 |
Correct |
11 ms |
5504 KB |
Output is correct |
8 |
Correct |
31 ms |
10624 KB |
Output is correct |
9 |
Correct |
35 ms |
10880 KB |
Output is correct |
10 |
Correct |
30 ms |
10488 KB |
Output is correct |
11 |
Correct |
24 ms |
8824 KB |
Output is correct |
12 |
Correct |
16 ms |
6528 KB |
Output is correct |
13 |
Correct |
34 ms |
8612 KB |
Output is correct |
14 |
Correct |
41 ms |
8440 KB |
Output is correct |
15 |
Correct |
23 ms |
6444 KB |
Output is correct |
16 |
Correct |
39 ms |
8440 KB |
Output is correct |
17 |
Correct |
27 ms |
8440 KB |
Output is correct |
18 |
Correct |
16 ms |
6528 KB |
Output is correct |
19 |
Correct |
26 ms |
8448 KB |
Output is correct |
20 |
Execution timed out |
2044 ms |
12024 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |