제출 #419029

#제출 시각아이디문제언어결과실행 시간메모리
419029codebuster_10Bitaro’s Party (JOI18_bitaro)C++17
14 / 100
1090 ms255180 KiB
#include <bits/stdc++.h> using namespace std ; #define int int64_t //be careful about this #define endl "\n" #define f(i,a,b) for(int i=int(a);i<int(b);++i) #define pr pair #define ar array #define fr first #define sc second #define vt vector #define pb push_back #define eb emplace_back #define LB lower_bound #define UB upper_bound #define PQ priority_queue #define sz(x) ((int)(x).size()) #define all(a) (a).begin(),(a).end() #define allr(a) (a).rbegin(),(a).rend() #define mem(a,b) memset(a, b, sizeof(a)) template<class A> void rd(vt<A>& v); template<class T> void rd(T& x){ cin >> x; } template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;} template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;} template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } template<typename T> void __p(T a) { cout<<a; } template<typename T, typename F> void __p(pair<T, F> a) { cout<<"{"; __p(a.first); cout<<","; __p(a.second); cout<<"}\n"; } template<typename T> void __p(std::vector<T> a) { cout<<"{"; for(auto it=a.begin(); it<a.end(); it++) __p(*it),cout<<",}\n"[it+1==a.end()]; } template<typename T, typename ...Arg> void __p(T a1, Arg ...a) { __p(a1); __p(a...); } template<typename Arg1> void __f(const char *name, Arg1 &&arg1) { cout<<name<<" : "; __p(arg1); cout<<endl; } template<typename Arg1, typename ... Args> void __f(const char *names, Arg1 &&arg1, Args &&... args) { int bracket=0,i=0; for(;; i++) if(names[i]==','&&bracket==0) break; else if(names[i]=='(') bracket++; else if(names[i]==')') bracket--; const char *comma=names+i; cout.write(names,comma-names)<<" : "; __p(arg1); cout<<" | "; __f(comma+1,args...); } void setIO(string s = "") { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin.exceptions(cin.failbit); cout.precision(15); cout << fixed; #ifdef ONLINE_JUDGE if(sz(s)){ freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } #define __f(...) 0 #endif } #undef int const int MAX_N = 100000, B = 317, inf = 1e9; pr<int,int> dis[MAX_N][B]; // 0 -> dis, 1 -> index bool rem[MAX_N]; int dp[MAX_N]; pr<int,int> tmp[B]; // merge as if(a.fr != b.fr) a.fr < b.fr else a.sc < b.sc; void check(pr<int,int> a[B]){ f(i,0,B-1){ assert(a[i].fr >= a[i+1].fr); if(a[i].fr == a[i+1].fr) assert(a[i].sc >= a[i+1].sc); } return; } void merge(pr<int,int> a[B], pr<int,int> b[B]){ check(a); check(b); f(i,0,B) tmp[i] = {-inf,-1}; int x = 0, y = 0, z = 0; while(z < B){ if(a[x].sc == -1 && b[y].sc == -1) break; if(a[x].fr == b[y].fr){ if(a[x].sc == b[y].sc){ tmp[z++] = a[x++] = b[y++]; }else{ if(a[x].sc > b[y].sc){ tmp[z++] = a[x++]; }else{ tmp[z++] = b[y++]; } } }else{ if(a[x].fr > b[y].fr){ tmp[z++] = a[x++]; }else{ tmp[z++] = b[y++]; } } } check(tmp); return; } signed main(){ setIO(); f(i,0,MAX_N) f(j,0,B) dis[i][j] = {-inf,-1}; mem(rem,false); int N,M,Q; rd(N,M,Q); vt<int> g[N]; f(_,0,M){ int u,v; rd(u,v); --u,--v; g[v].pb(u); } f(i,0,N){ dis[i][0] = {-1,i}; for(auto j : g[i]){ merge(dis[i],dis[j]); f(j,0,B) dis[i][j] = tmp[j]; } f(k,0,B) if(dis[i][k].fr != -inf) ++dis[i][k].fr; } // f(i,0,N){ // __f("i",i+1); // f(j,0,10){ // cout << dis[i][j].sc + 1 << ' '; // } // cout << endl; // } f(_,0,Q){ int T,Y; rd(T,Y); --T; vt<int> C(Y); for(auto& i : C) cin >> i, --i; for(auto& i : C) rem[i] = true; if(Y < B){ bool done = false; f(i,0,B){ if(dis[T][i].sc != -1 && !rem[dis[T][i].sc]){ cout << dis[T][i].fr << endl; done = true; break; } } if(!done) cout << -1 << endl; }else{ f(i,0,N) dp[i] = -inf; dp[T] = 0; for(int i = T; i >= 0; --i){ for(auto j : g[i]){ ckmax(dp[j],dp[i]+1); } } int ans = -1; f(i,0,N){ if(!rem[i]) ckmax(ans,dp[i]); } cout << ans << endl; } for(auto& i : C) rem[i] = false; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...