제출 #963258

#제출 시각아이디문제언어결과실행 시간메모리
963258TimAniBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2066 ms32340 KiB
//start-time: 2024-04-14 19:39:32 #include <bits/stdc++.h> using namespace std; using ll = long long; void solve(){ ll n, m, q; cin >> n >> m >> q; vector<vector<ll>> g(n); vector<vector<ll>> gR(n); for(ll i = 0; i < m; i++){ ll u, v; cin >> u >> v; u--; v--; g[u].push_back(v); gR[v].push_back(u); } vector<ll> vis(n), topo; auto dfs = [&](ll u, auto&&dfs) -> void { vis[u] = 1; for(auto v : g[u]){ if(!vis[v]){ dfs(v, dfs); } } vis[u] = 2; topo.push_back(u); }; for(int i = 0; i < n; i++){ if(vis[i] == 0){ dfs(i, dfs); } } reverse(topo.begin(), topo.end()); vector<set<array<ll, 2>>> dp(n); vector<bitset<100'001>> cnt(n); //map<int, map<int, ll>> mp; for(auto el : topo){ dp[el].insert({0, el}); //mp[el][el] = 0; cnt[el][el] = 1; } const ll w = round(sqrt(100000)) + 1; for(auto u : topo){ for(auto v : gR[u]){ for(auto [val, i] : dp[v]){ cnt[u] |= cnt[v]; ll o = val + 1; //if(mp[u][i]) { //o = max(o, mp[u][i]); //dp[u].erase({mp[u][i], i}); //} //mp[u][i] = o; dp[u].insert({o, i}); if(dp[u].size() > w){ auto [V, I] = *dp[u].begin(); dp[u].erase(dp[u].begin()); //mp[u][I] = 0; } } } } for(ll i = 0; i < q; i++){ ll u, y; cin >> u >> y; u--; bitset<100'001> c; for(ll j = 0; j < y; j++){ ll a; cin >> a; c[--a] = 1; } if((cnt[u] & c) == cnt[u]){ cout << -1 << endl; continue; } ll ans = 0; if(y < w){ set<array<ll, 2>> ms = dp[u]; for(auto [v, i] : ms){ if(!c[i]){ ans = max(ans, v); } } } else{ vector<int> naive(n); for(auto v : topo){ naive[v] = c[v] ? -1 : 0; for(auto el : gR[v]){ naive[v] = max(naive[v], naive[el] + (naive[el] != -1)); } } ans = naive[u]; } //for(auto el : naive){ //cout << el << ' '; //} //cout << endl; cout << ans << endl; } } int main() { cin.tie(0)->sync_with_stdio(0); ll T = 1; //cin >> T; while(T--) solve(); return 0; }

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

bitaro.cpp: In function 'void solve()':
bitaro.cpp:65:26: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   65 |                     auto [V, I] = *dp[u].begin();
      |                          ^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...