#include <bits/stdc++.h>
#define D 303
#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);
}
mar[t]=true;
if(false){
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);
}
mar[t]=false;
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:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<d[t].size();i++){
~^~~~~~~~~~~~
bitaro.cpp:88: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 |
Incorrect |
7 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
