제출 #1261150

#제출 시각아이디문제언어결과실행 시간메모리
1261150GoodBitaro’s Party (JOI18_bitaro)C++20
14 / 100
2101 ms411584 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; using vi = vector<int>; using vll = vector<ll>; using vpii = vector<pii>; using vpll = vector<pll>; #define endl '\n' #define pb push_back #define eb emplace_back #define ff first #define ss second #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) (int)(x).size() #define rep(i, a, b) for (int i = (a); i < (b); ++i) #define rev(i, a, b) for (int i = (a); i >= (b); --i) const ll inf = 1e18; const int mod = 1e9 + 7; const int maxn = 2e5 + 5; void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); } vector<bool> vis; vi d; vpii dist; vector<vi> a; vector<vpii> b; void solve() { int n, m, q, u, v; cin >> n >> m >> q; a.resize(n + 1); b.resize(n + 1); dist.resize(n + 1); vis.resize(n + 1); d.resize(n + 1); int block = 500; rep(i, 0, m) { cin >> u >> v; a[v].pb(u); } vi c(n + 1, 0); rep(i, 1, n + 1) { rep(j, 0, block) { pii nd = {0, 0}; int cur = 0; for(int &k: a[i]) { while(c[k] < b[k].size() && vis[b[k][c[k]].ss]) c[k]++; if (c[k] < b[k].size() && b[k][c[k]].ff + 1 > nd.ff && !vis[b[k][c[k]].ss]) nd = {b[k][c[k]].ff + 1, b[k][c[k]].ss}, cur = k; else if (c[k] == b[k].size() && 1 > nd.ff && !vis[k]) nd = {1, k}, cur = k; } // cout << "filling " << i << ' ' << nd.ff << ' ' << nd.ss << endl; if (nd.ss != 0) b[i].pb(nd), vis[nd.ss] = 1, c[cur]++; else break; } for(int &j: a[i]) c[j] = 0; rep(j, 0, sz(b[i])) vis[b[i][j].ss] = 0; } // rep(i, 1, n + 1) { // cout << i << " ==== "; // for (pii &j: b[i]) cout << j.ss << ' '; // cout << endl; // } rep(i, 1, n + 1) dist[i] = {0, i}; while(q--) { int t, y; auto clear = [](int y) { rep(i, 0, y) vis[d[i]] = 0; }; cin >> t >> y; rep(i, 0, y) cin >> d[i], vis[d[i]] = 1; bool flag = 0; for (pii &i: b[t]) if (!vis[i.ss]) { cout << i.ff << '\n'; flag = true; break; } if (flag) {clear(y); continue;} rep(i, 1, n + 1) { for (int &j: a[i]) { if (dist[j].ff + 1 > dist[i].ff && !vis[dist[j].ss]) dist[i] = {dist[j].ff + 1, dist[j].ss}; } } if (!dist[t].ff && vis[t]) cout << -1 << '\n'; else cout << dist[t].ff << '\n'; rep(i, 1, n + 1) vis[i] = 0, dist[i] = {0, i}; } } int main() { // freopen("file.in", "r", stdin); // freopen("file.out", "w", stdout); fast_io(); int t = 1; while (t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...