Submission #751466

#TimeUsernameProblemLanguageResultExecution timeMemory
751466Valters07Bitaro’s Party (JOI18_bitaro)C++14
7 / 100
2011 ms389596 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") #define fio ios_base::sync_with_stdio(0);cin.tie(0); #define ll long long #define en cin.close();return 0; #define pb push_back #define fi first//printf("%lli\n",cur); #define se second//scanf("%lli",&n); using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int N = 1e5+5; const int B = 80; vector<int> g[N]; set<pair<int,int> > best[N]; int main() { fio // ifstream cin("in.in"); int n, m, q; cin >> n >> m >> q; while(m--) { int u, v; cin >> u >> v; g[u].pb(v); } for(int i = 1;i<=n;i++) best[i].insert({0,i}); for(int i = 1;i<=n;i++) { for(auto j:g[i]) { for(auto x:best[i])//the cursed time complexity { best[j].insert({x.fi+1,x.se}); if(best[j].size()>B) best[j].erase(best[j].begin()); } } } for(int qi = 1;qi<=q;qi++) { int f, y; cin >> f >> y; vector<int> del(y); for(auto &x:del) cin >> x; if(y<B) { set<int> s; for(auto x:del) s.insert(x); auto t = --best[f].end(); while(t!=best[f].begin()&&s.count((*t).se)) t--; if(s.count((*t).se)) cout << -1; else cout << (*t).fi; } else { vector<int> dist(n+1); for(auto x:del) dist[x]=-1e9; for(int i = 1;i<=f;i++) for(auto j:g[i]) dist[j]=max(dist[j],dist[i]+1); if(dist[f]<0) cout << -1; else cout << dist[f]; } cout << "\n"; } // cin.close(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...