제출 #967453

#제출 시각아이디문제언어결과실행 시간메모리
967453Tuanlinh123Bitaro’s Party (JOI18_bitaro)C++17
14 / 100
2066 ms228500 KiB
#include<bits/stdc++.h> #define ll int #define pll pair<ll, ll> #define pb push_back #define mp make_pair #define fi first #define se second #define ld long double #define sz(a) ((ll)(a).size()) using namespace std; const ll maxn=100005, s=130; ll deg[maxn], seen[maxn]; vector <pll> best[maxn]; vector <ll> A[maxn], At[maxn]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, m, q; cin >> n >> m >> q; for (ll i=1; i<=m; i++) { ll u, v; cin >> u >> v; A[u].pb(v), At[v].pb(u), deg[v]++; } queue <ll> Q; for (ll i=1; i<=n; i++) if (!deg[i]) Q.push(i); while (sz(Q)) { ll u=Q.front(); Q.pop(); vector <pll> val; ll sum=0; for (ll v:At[u]) sum+=sz(best[v]); val.reserve(sum+5), val.pb({-1, u}); for (ll v:At[u]) for (pll b:best[v]) val.pb(b); sort(val.begin(), val.end(), greater<pll>()); for (auto [x, v]:val) if (!seen[v]) { seen[v]=1, best[u].pb({x+1, v}); if (sz(best[u])==s) break; } for (auto [x, v]:best[u]) seen[v]=0; for (ll v:A[u]) { deg[v]--; if (!deg[v]) Q.push(v); } } for (ll i=1; i<=q; i++) { ll X, x, ans=-1; cin >> X >> x; vector <ll> a(x); for (ll &i:a) cin >> i; if (x>=s) { queue <ll> q; vector <ll> dp(n+5, 0), deg(n+5, 0); for (ll i=1; i<=n; i++) deg[i]=sz(At[i]), !deg[i]?q.push(i),0:0; for (ll i:a) dp[i]=-1e9; while (sz(q)) { ll u=q.front(); q.pop(); for (ll v:At[u]) dp[u]=max(dp[u], dp[v]+1); for (ll v:A[u]) { deg[v]--; if (!deg[v]) q.push(v); } } if (dp[X]>=0) ans=dp[X]; } else { for (ll j:a) seen[j]=1; for (auto [x, v]:best[X]) if (!seen[v]) {ans=x; break;} for (ll j:a) seen[j]=0; } cout << ans << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...