Submission #458734

#TimeUsernameProblemLanguageResultExecution timeMemory
458734zeyuBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2001 ms205928 KiB
#include <bits/stdc++.h> #define maxn 100010 using namespace std; const int B = 200; int n, m, q; typedef pair<int, int> pi; vector<int> prv[maxn]; vector<pi> far[maxn]; vector<int> vis(maxn, -1), val(maxn); vector<int> y(maxn, -1); int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> q; for (int i = 0; i < m; i ++){ int x, y; cin >> x >> y; x --; y --; prv[y].push_back(x); } for (int i = 0; i < n; i ++){ vector<int> all; vector<int> dist[B]; for (int j = 0; j < (int)prv[i].size(); j ++){ int x = prv[i][j]; for (int k = 0; k < (int)far[x].size(); k ++){ int z = far[x][k].second; if (vis[z] != i){ vis[z] = i; all.push_back(z); val[z] = far[x][k].first + 1; } else{ val[z] = max(val[z], far[x][k].first + 1); } } if (vis[x] != i){ vis[x] = i; all.push_back(x); val[x] = 1; } } all.push_back(i); val[i] = 0; for (int j = 0; j < (int)all.size(); j ++){ if (val[all[j]] < B) dist[val[all[j]]].push_back(all[j]); } int cnt = 0; for (int k = B - 1; k >= 0; k --){ for (int j = 0; j < (int)dist[k].size(); j ++){ far[i].push_back(make_pair(k, dist[k][j])); cnt ++; if (cnt == B) goto flag; } } flag: continue; } while(q --){ int t; cin >> t; t --; int r; cin >> r; for (int i = 0; i < r; i ++){ int p; cin >> p; y[p - 1] = q; } if (r >= B){ vector<int> dp(n, -1); for (int i = 0; i <= t; i ++){ if (y[i] != q){ dp[i] = max(dp[i], 0); } for (int j = 0; j < (int)prv[i].size(); j ++){ if (dp[prv[i][j]] != -1) dp[i] = max(dp[i], dp[prv[i][j]] + 1); } } cout << dp[t] << '\n'; } else{ for (int i = 0; i < (int)far[t].size(); i ++){ if (y[far[t][i].second] != q){ cout << far[t][i].first << '\n'; goto done; } } cout << -1 << '\n'; done: continue; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...