제출 #90475

#제출 시각아이디문제언어결과실행 시간메모리
90475radoslav11Bitaro’s Party (JOI18_bitaro)C++17
14 / 100
2068 ms131268 KiB
#include <bits/stdc++.h> #define endl '\n' #pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace std; template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; } template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; } const int MAXN = (int)1e5 + 17 + 42; const int B = 60; int n, m, q; vector<int> adj[MAXN]; void read() { cin >> n >> m >> q; for(int i = 0; i < m; i++) { int u, v; cin >> u >> v; adj[v].push_back(u); } } bool ok[MAXN]; int _dp[MAXN]; int Tm_vis[MAXN], cnt_t; int TMS = 0; vector<pair<int, int> > dp[MAXN]; int rec(int u) { if(Tm_vis[u] >= cnt_t) return _dp[u]; Tm_vis[u] = cnt_t; if(ok[u]) _dp[u] = 0; else _dp[u] = -1e9; for(int v: adj[u]) chkmax(_dp[u], rec(v) + 1); return _dp[u]; } int solve_brute(int u, vector<int> blocked) { for(int x: blocked) ok[x] = 0; cnt_t++; int ans = rec(u); for(int x: blocked) ok[x] = 1; return ans < 0 ? -1 : ans; } bool same[MAXN]; bool cmp(pair<int, int> a, pair<int, int> b) { return a.second > b.second; } void solve() { for(int i = 1; i <= n; i++) ok[i] = 1; for(int u = 1; u <= n; u++) { dp[u].push_back({u, 0}); for(auto v: adj[u]) for(auto it: dp[v]) dp[u].push_back({it.first, it.second + 1}); sort(dp[u].begin(), dp[u].end()); vector<pair<int, int> > rl; for(auto it: dp[u]) if(rl.empty() || rl.back().first != it.first) rl.push_back(it); else rl[rl.size() - 1].second = it.second; if(rl.size() > B) { sort(rl.begin(), rl.end(), cmp); while((int)rl.size() > B) rl.pop_back(); } dp[u] = rl; } while(q--) { int st, sz; vector<int> li; cin >> st >> sz; bool has_large = 0; for(int i = 0; i < sz; i++) { int x; cin >> x; li.push_back(x); } vector<int> initial_li = li; if(li.size() >= B) { cout << solve_brute(st, li) << endl; continue; } for(auto it: li) same[it] = 1; int answer = 0; for(auto it: dp[st]) if(!same[it.first]) chkmax(answer, it.second); for(auto it: li) same[it] = 0; if(answer < 0) answer = -1; if(answer == 0) { for(auto it: initial_li) if(it == st) answer = -1; } cout << answer << endl; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); read(); solve(); return 0; }

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

bitaro.cpp: In function 'void solve()':
bitaro.cpp:93:8: warning: unused variable 'has_large' [-Wunused-variable]
   bool has_large = 0;
        ^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...