Submission #1060380

#TimeUsernameProblemLanguageResultExecution timeMemory
1060380doducanhBitaro’s Party (JOI18_bitaro)C++14
0 / 100
3 ms5724 KiB
///breaker #include<bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define ii pair<int,int> #define mp make_pair #define in(x) freopen(x,"r",stdin) #define out(x) freopen(x,"w",stdout) #define bit(x,i) ((x>>i)&1) const int maxn=1e5+7; int n,m,q; int block_size=100; vector<int>radj[maxn]; void sol() { cin>>n>>m>>q; for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; radj[v].push_back(u); } vector<vector<ii>>path_sizes(n+1); vector<int>from(n+1,-1); for(int i=1;i<=n;i++){ path_sizes[i].push_back({0,i}); vector<int>fromid; for(int j:radj[i]){ for(auto [dist,idx]:path_sizes[j]){ if(from[idx]!=-1){ from[idx]=max(from[idx],dist+1); } else{ fromid.push_back(idx); from[idx]=dist+1; } } } for(int idx:fromid){ path_sizes[i].push_back({from[idx],idx}); } sort(path_sizes[i].rbegin(),path_sizes[i].rend()); while(path_sizes[i].size()>block_size)path_sizes.pop_back(); for(int idx:fromid){ from[idx]=-1; } } while(q--){ int t,v; cin>>t>>v; vector<bool>cvst(n+1,0); for(int i=0;i<v;i++){ int x; cin>>x; cvst[x]=1; } int ans=-1; if(v>=block_size){ vector<int>dp(t+1,-1); dp[t]=0; for(int i=t;i>=1;i--){ if(dp[i]==-1)continue; if(cvst[i]==0)ans=max(ans,dp[i]); for(int j:radj[i]){ dp[j]=max(dp[j],dp[i]+1); } } } else{ for(auto [dist,idx]:path_sizes[t]){ if(cvst[idx]==0){ ans=dist; break; } } } cout<<ans<<"\n"; } } main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t=1; while(t--){ sol(); } // you should actually read the stuff at the bottom return 0; } /* stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH */

Compilation message (stderr)

bitaro.cpp: In function 'void sol()':
bitaro.cpp:30:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |             for(auto [dist,idx]:path_sizes[j]){
      |                      ^
bitaro.cpp:44:35: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |         while(path_sizes[i].size()>block_size)path_sizes.pop_back();
      |               ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
bitaro.cpp:71:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |             for(auto [dist,idx]:path_sizes[t]){
      |                      ^
bitaro.cpp: At global scope:
bitaro.cpp:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   81 | main()
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...