Submission #255539

#TimeUsernameProblemLanguageResultExecution timeMemory
255539uacoder123Bitaro’s Party (JOI18_bitaro)C++14
7 / 100
1230 ms524292 KiB
#include <bits/stdc++.h> using namespace std; #define F first #define S second #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i) #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i) #define all(x) (x).begin(), (x).end() #define sz(x) int(x.size()) #define mp(i,a) make_pair(i,a) #define pb(a) push_back(a) #define bit(x,b) (x&(1LL<<b)) typedef long long int lli; typedef pair <lli,lli> ii; typedef pair <lli,ii> iii; typedef vector <lli> vi; vi al[100001]; vector<ii> lis[100001]; int vis[100001],vis1[100001],ans[100001]; int r=270,co=0; vector<int> freq[100001]; int vis2[100001],n; void dfs() { for(int k=1;k<=n;++k) { lli ma=0; for(int i=0;i<al[k].size();++i) { for(int j=0;j<lis[al[k][i]].size();++j) { freq[1+lis[al[k][i]][j].F].pb(lis[al[k][i]][j].S); ma=max(ma,1+lis[al[k][i]][j].F); } } freq[0].pb(k); while(lis[k].size()<r) { if(freq[ma].size()==0) ma-=1; if(ma==-1) break; if(!vis2[freq[ma].back()]) { lis[k].pb(mp(ma,freq[ma].back())); vis2[freq[ma].back()]=1; } freq[ma].pop_back(); } for(int i=0;i<lis[k].size();++i) vis2[lis[k][i].S]=0; for(int i=0;i<al[k].size();++i) for(int j=0;j<lis[al[k][i]].size();++j) if(freq[lis[al[k][i]][j].F+1].size()>0) freq[lis[al[k][i]][j].F+1].clear(); freq[0].clear(); } } void dfs1(int node) { ans[node]=0; vis1[node]=1; for(int i=0;i<al[node].size();++i) { if(vis1[al[node][i]]==0) { dfs1(al[node][i]); } ans[node]=max(ans[node],1+ans[al[node][i]]); } if(ans[node]==0&&vis[node]==1) ans[node]=-1; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int m,q; cin>>n>>m>>q; for(int i=0;i<m;++i) { int f,s; cin>>f>>s; al[s].pb(f); } dfs(); vi v; for(int i=0;i<q;++i) { int s,no; cin>>s>>no; int an=-1; for(int j=0;j<no;++j) { int f; cin>>f; vis[f]=1; v.pb(f); } for(auto j=0;j<lis[s].size();++j) { if(vis[lis[s][j].S]==0) { an=lis[s][j].F; break; } } if(an==-1&&no>=r) { memset(vis1,0,sizeof(vis1)); dfs1(s); an=ans[s]; } for(int j=0;j<v.size();++j) vis[v[j]]=0; v.clear(); cout<<an<<'\n'; } return 0; }

Compilation message (stderr)

bitaro.cpp: In function 'void dfs()':
bitaro.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<al[k].size();++i)
                   ~^~~~~~~~~~~~~
bitaro.cpp:30:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<lis[al[k][i]].size();++j)
                     ~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:37:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(lis[k].size()<r)
             ~~~~~~~~~~~~~^~
bitaro.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<lis[k].size();++i)
                   ~^~~~~~~~~~~~~~
bitaro.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<al[k].size();++i)
                   ~^~~~~~~~~~~~~
bitaro.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<lis[al[k][i]].size();++j)
                     ~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'void dfs1(int)':
bitaro.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<al[node].size();++i)
                   ~^~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:100:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(auto j=0;j<lis[s].size();++j)
                      ~^~~~~~~~~~~~~~
bitaro.cpp:114:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<v.size();++j)
                     ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...