Submission #111068

#TimeUsernameProblemLanguageResultExecution timeMemory
111068igziBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2044 ms12024 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...