제출 #329840

#제출 시각아이디문제언어결과실행 시간메모리
329840VROOM_VARUNBitaro’s Party (JOI18_bitaro)C++14
14 / 100
2037 ms89712 KiB
/* ID: varunra2 LANG: C++ TASK: bitaro */ #include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "lib/debug.h" #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define debug_arr(...) \ cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__) #pragma GCC diagnostic ignored "-Wsign-compare" //#pragma GCC diagnostic ignored "-Wunused-parameter" //#pragma GCC diagnostic ignored "-Wunused-variable" #else #define debug(...) 42 #endif #define EPS 1e-9 #define IN(A, B, C) assert(B <= A && A <= C) #define INF (int)1e9 #define MEM(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define MP make_pair #define PB push_back #define all(cont) cont.begin(), cont.end() #define rall(cont) cont.end(), cont.begin() #define x first #define y second const double PI = acos(-1.0); typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef map<int, int> MPII; typedef multiset<int> MSETI; typedef set<int> SETI; typedef set<string> SETS; typedef vector<int> VI; typedef vector<PII> VII; typedef vector<VI> VVI; typedef vector<string> VS; #define rep(i, a, b) for (int i = a; i < (b); ++i) #define trav(a, x) for (auto& a : x) #define sz(x) (int)(x).size() typedef pair<int, int> pii; typedef vector<int> vi; #pragma GCC diagnostic ignored "-Wsign-compare" // util functions const int block = 400; int n, m, q; vector<bool> vis; VVI adj; vector<VII> vals; VII comb(VI& inds, int pos) { // the size of each vector is <= block int siz = sz(inds); if (siz == 0) { return {MP(0, pos)}; } priority_queue<pair<PII, int>> pq; VI ind(siz, 0); VII ret; map<int, bool> use; for (int i = 0; i < siz; i++) { pq.push(MP(vals[inds[i]][0], i)); } int cnt = 0; while (sz(ret) < block) { auto x = pq.top(); pq.pop(); if (!use[x.x.y]) { use[x.x.y] = true; ret.PB(MP(x.x.x + 1, x.x.y)); } ind[x.y]++; if (ind[x.y] < sz(vals[inds[x.y]])) { pq.push(MP(vals[inds[x.y]][ind[x.y]], x.y)); } else if (ind[x.y] == sz(vals[inds[x.y]])) cnt++; if (cnt == siz) break; } ret.PB(MP(0, pos)); return ret; } void init() { adj.resize(n); vals.resize(n); vis.assign(n, false); } void gen(int u) { vals[u] = comb(adj[u], u); } void preprocess() { for (int i = 0; i < n; i++) { gen(i); } } void stupid(VI& dist) { for (int i = n - 1; ~i; i--) { if (dist[i] == -1) continue; for (auto& x : adj[i]) dist[x] = max(dist[x], dist[i] + 1); } } int main() { // #ifndef ONLINE_JUDGE // freopen("bitaro.in", "r", stdin); // freopen("bitaro.out", "w", stdout); // #endif cin.sync_with_stdio(0); cin.tie(0); cin >> n >> m >> q; init(); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; u--, v--; adj[v].PB(u); } bool calc = false; while (q--) { int u, cnt; cin >> u >> cnt; u--; map<int, bool> bad; for (int i = 0; i < cnt; i++) { int v; cin >> v; v--; bad[v] = true; } if (cnt < block - 1) { if (!calc) { calc = true; preprocess(); } int ret = -1; for (int i = 0; i < sz(vals[u]); i++) { if (!bad[vals[u][i].y]) { ret = vals[u][i].x; break; } } cout << ret << '\n'; } else { VI dist(n, -1); dist[u] = 0; stupid(dist); int ret = -1; for (int i = 0; i < n; i++) { if (bad[i]) continue; ret = max(ret, dist[i]); } cout << ret << '\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...