Submission #1095934

#TimeUsernameProblemLanguageResultExecution timeMemory
1095934mohammad86Bitaro’s Party (JOI18_bitaro)C++17
14 / 100
1305 ms419548 KiB
// https://oj.uz/problem/view/JOI18_bitaro #include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; const int maxn = 1e5 + 100; const int sqrtn = 320; int n, m, q; vector<int> adj[maxn]; vector<int> readj[maxn]; vector<pii> fv[maxn]; bool mark[maxn]; int main () { ios_base::sync_with_stdio(false); cin >> n >> m >> q; for (int i = 1; i <= m; i++) { int s, e; cin >> s >> e; adj[s].push_back(e); readj[e].push_back(s); } for (int i = 1; i <= n; i++) { vector<pii> tmp; tmp.push_back({0, i}); for (int k = 0 ; k <= sqrtn; k++) { for (int j : readj[i]) { if (int(fv[j].size()) > k) { tmp.push_back({fv[j][k].first+1, fv[j][k].second}); } } if (tmp.size() > sqrtn) { break; } } sort(tmp.begin(), tmp.end(), greater<pii>()); for (int j = 0; j < min(int(tmp.size()), sqrtn); j++) { fv[i].push_back(tmp[j]); } } for (int i = 1; i <= q; i++) { int t, y; cin >> t >> y; vector<int> tmp; for (int i = 0; i < y; i++) { int c; cin >> c; tmp.push_back(c); mark[c] = true; } if (y < sqrtn) { bool is_find = false; for (pii i : fv[t]) { if (!mark[i.second]) { cout << i.first << endl; is_find = true; break; } } if (!is_find) { cout << -1 << endl; } } else { vector<int> dis(t+2, -1); int maximum = -1; dis[t] = 0; if (!mark[t]) { maximum = 0; } for (int i = t-1; i >= 1; i--) { dis[i] = -1; for (int j : adj[i]) { if (j > t || dis[j] == -1) { continue; } dis[i] = max(dis[i], dis[j] +1); } if (!mark[i]) maximum = max(maximum, dis[i]); } cout << maximum << endl; } for (int i = 0; i < y; i++) { mark[tmp[i]] = false; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...