제출 #1251742

#제출 시각아이디문제언어결과실행 시간메모리
1251742tkm_algorithmsBitaro’s Party (JOI18_bitaro)C++20
0 / 100
12 ms9032 KiB
/** * In the name of Allah * We are nothing and you're everything * Ya Muhammad! **/ #include <bits/stdc++.h> #ifdef LOCAL #define debug(x) cerr << #x << "= " << x << endl; #else #define debug(x) #endif using namespace std; using ll = long long; using ull = uint64_t; #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() #define mp(x, y) make_pair(x, y) //#define int long long const char nl = '\n'; const int N = 1e5+5; const int inf = 1e9; vector<int> g[N]; vector<pair<int, int>> mx[N]; const int bl = 318; void solve() { int n, m, qu; cin >> n >> m >> qu; for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; g[b].push_back(a); } vector<int> pos(n+1); for (int i = 1; i <= n; ++i) { priority_queue<pair<pair<int, int>, int>> pq; for (auto j: g[i])pq.push({mx[j][0], j}); int cnt = 0; while (sz(mx[i])<bl && sz(pq)>0) { mx[i].push_back({pq.top().first.first+1, pq.top().first.second}); pos[pq.top().second] += 1; if (pos[pq.top().second] == sz(mx[pq.top().second]))cnt += 1; else { pq.push({mx[pq.top().second][pos[pq.top().second]], pq.top().second}); } pq.pop(); } for (auto j: g[i])pos[j] = 0; mx[i].push_back({0, i}); } vector<int> v(n+1); for (int i = 0; i < qu; ++i) { int t, y; cin >> t >> y; vector<int> c(y); for (auto &j: c) { cin >> j; //cout << j << " "; v[j] = 1; } //cout << nl; bool res = true; for (auto j: mx[t]) if (!v[j.second]) { cout << j.first << nl; res = false; break; } if (res) { //cout << v[1] << nl; vector<int> dp(n+1); for (int ii = 1; ii <= n; ++ii) { if (!v[ii])dp[ii] = 0; else dp[ii] = -inf; for (auto j: g[ii]) dp[ii] = max(dp[ii], dp[j]+1); } if (dp[t]<0)cout << -1 << nl; else cout << dp[t] << nl; } for (auto j: c)v[j] = 0; } } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); //int t; cin >> t; //while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...