제출 #674368

#제출 시각아이디문제언어결과실행 시간메모리
674368KahouBitaro’s Party (JOI18_bitaro)C++14
0 / 100
5 ms5204 KiB
/* In the name of God, aka Allah */ // let this be mytemp.cpp #include<bits/stdc++.h> using namespace std; #define F first #define S second #define endl '\n' #define mk make_pair typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int inf = 1e9 + 50; const int N = 1e5 + 50, SQ = 315; int n, m, q, pd[N]; bool mark[N]; pii dp[N][SQ], tmp[SQ]; vector<int> adj[N]; void push(int u, int v) { int p1 = 0, p2 = 0; for (int i = 0; i < SQ; i++) { if (p1 < SQ && (p2 >= SQ || (p2 < SQ && dp[v][p1].F > dp[u][p2].F))) tmp[i] = dp[v][p1++]; else tmp[i] = dp[u][p2++], tmp[i].F++; } for (int i = 0; i < SQ; i++) { dp[v][i] = tmp[i]; } } void solve() { cin >> n >> m >> q; for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); } for (int u = 1; u <= n; u++) { dp[u][0] = {0, u}; for (int i = 1; i < SQ; i++) { dp[u][i] = {-inf, 0}; } } for (int u = 1; u <= n; u++) { for (int v:adj[u]) { push(u, v); } } vector<int> vc; while (q--) { int x, s; cin >> x >> s; vc.clear(); int ans = 0; for (int i = 1; i <= s; i++) { int v; cin >> v; vc.push_back(v); } if (s < SQ) { for (int u:vc) mark[u] = 1; for (int i = 0; i < SQ; i++) { if (mark[dp[x][i].S]) continue; ans = dp[x][i].F; break; } for (int v:vc) mark[v] = 0; } else { for (int u = 1; u <= n; u++) pd[u] = 0; for (int u:vc) pd[u] = -1; for (int u = 1; u <= n; u++) { for (int v:adj[u]) { pd[v] = max(pd[v], pd[u]+1); } } ans = pd[x]; } cout << (ans < 0? -1 : ans) << endl; } } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...