제출 #1054484

#제출 시각아이디문제언어결과실행 시간메모리
1054484MinbaevBitaro’s Party (JOI18_bitaro)C++17
0 / 100
22 ms21296 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast,unroll-loops") using namespace std; using namespace __gnu_pbds; #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define f first #define s second #define int long long #define ll long long #define pii pair<int,int> #define ar array template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;} template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;} template<class T> using st = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; const int inf = 1e17 + 7; const int mod = 1e9 + 7; const int N = 3e5 + 5; const int md = 998244353; int binpow(int a, int b){ if(b == 0)return 1; if(b % 2 == 0){ int c = binpow(a,b/2); return (c*c)%mod; } return (binpow(a,b-1)*a)%mod; } int divi(int a, int b){ return (a*(binpow(b,mod-2)))%mod; } int n,m,k; int sz = 400; vector<int>g[N]; vector<ar<int,2>>calc[N]; void solve(){ cin >> n >> m >> k; while(m--){ int a,b; cin >> a >> b; //~ g[a].pb(b); g[b].pb(a); } vector<int>reach, dist(n+1), last(n+1); for(int i = 1;i<=n;i++){ reach.pb(i); for(auto x:g[i]){ for(auto [cost, to] : calc[x]){ if(last[to] == i){ umax(dist[to], cost + 1); } else { dist[to] = cost + 1; last[to] = i; reach.pb(to); } } } sort(all(reach),[&](int a, int b){ return dist[a] > dist[b]; }); for(int j = 0;j<min(sz, (int)reach.size());j++){ calc[i].pb({dist[reach[j]],reach[j]}); } reach.clear(); } vector<int>vis(n+1); while(k--){ int a,b,c; cin >> a >> b; vector<int>vs; for(int i = 1;i<=b;i++){ cin >> c; vis[c] = 1; vs.pb(c); } if(b < sz){ vector<int>dis(n+1); queue<int>q; q.push(a); while(!q.empty()){ auto x = q.front(); q.pop(); for(auto to:g[x]){ if(umax(dis[to], dis[x] + 1)){ q.push(to); } } } int mx = -1; for(int i = 1;i<=n;i++){ if(vis[i] || dis[i] == 0 && i != a)continue; umax(mx, dis[i]); } cout << mx << "\n"; } else{ for(auto [cost, to] : calc[a]){ if(vis[to])continue; cout << cost << "\n"; break; } } for(auto to:vs)vis[to] = 0; } } /* 5 6 1 5 3 5 4 3 1 3 2 4 2 2 1 2 1 5 1 2 3 4 4 3 1 2 5 */ signed main() { // freopen("seq.in", "r", stdin); // freopen("seq.out", "w", stdout); ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); int tt=1;//cin>>tt; while(tt--)solve(); }

컴파일 시 표준 에러 (stderr) 메시지

bitaro.cpp: In function 'void solve()':
bitaro.cpp:112:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  112 |     if(vis[i] || dis[i] == 0 && i != a)continue;
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...