Submission #396163

#TimeUsernameProblemLanguageResultExecution timeMemory
396163pure_memBitaro’s Party (JOI18_bitaro)C++14
7 / 100
2093 ms115332 KiB
#include <bits/stdc++.h> #define X first #define Y second #define MP make_pair #define ll long long using namespace std; const int N = 1e5 + 1, BS = 300; const ll INF = 1e18; int n, m, q, dsu[N], used[N], cnt[N], dp[N]; vector< int > g[N]; vector< pair<int, int> > gg[N]; void prep(){ cin >> n >> m >> q; for(int i = 1, x, y;i <= m;i++){ cin >> x >> y; g[y].push_back(x); } set< pair<int, int> > act; for(int i = 1;i <= n;i++){ gg[i].push_back(MP(0, i)); for(int from: g[i]){ for(pair<int, int> tmp: gg[from]){ if(used[tmp.Y] != i) dp[tmp.Y] = 0, used[tmp.Y] = i; if(tmp.X + 1 > dp[tmp.Y]){ act.erase(MP(dp[tmp.Y], tmp.Y)); dp[tmp.Y] = tmp.X + 1; act.insert(MP(dp[tmp.Y], tmp.Y)); if(act.size() > BS) used[act.begin()->Y] = -1, act.erase(act.begin()); } } } while(!act.empty()){ gg[i].push_back(*act.begin()); act.erase(act.begin()); } act.clear(); } } int main () { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); prep(); for(int pos, len, x, T = N + 1;q--;T++){ cin >> pos >> len; for(int j = 1;j <= len;j++){ cin >> x, used[x] = T; } if(len > BS){ for(int i = 1;i <= pos;i++){ dp[i] = 0, cnt[i] = 0; if(used[i] != T) cnt[i] = 1; for(int from: g[i]){ if(dp[from] + 1 > dp[i] && cnt[from]) dp[i] = dp[from] + 1, cnt[i] = cnt[from]; else if(dp[from] + 1 == dp[i] && cnt[from]) cnt[i]++; } } } else { dp[pos] = 0, cnt[pos] = 0; for(pair<int, int> tmp: gg[pos]){ if(used[tmp.Y] == T) continue; if(tmp.X > dp[pos]) dp[pos] = tmp.X, cnt[pos] = 1; else if(tmp.X == dp[pos]) cnt[pos]++; } } cout << (cnt[pos] == 0 ? -1: dp[pos]) << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...