Submission #928296

#TimeUsernameProblemLanguageResultExecution timeMemory
928296dostsBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2023 ms36888 KiB
#pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> using namespace std; #define sp << " " << #define int long long #define vi vector<int> #define all(x) x.begin(),x.end() #define pii pair<int,int> #define wtf {cout << "OK\n"; return;} const int N = 1e5+1,MOD = 998244353,B = 350,inf = 2e18; void solve() { int n,m,q; cin >> n >> m >> q; vi edges[n+1],egdes[n+1],inc(n+1,0),vis(n+1,0); for (int i=1;i<=m;i++) { int a,b; cin >> a >> b; edges[a].push_back(b); egdes[b].push_back(a); inc[b]++; } vector<set<pii>> gnomes(n+1); vector<set<pii>> gotgnomes(n+1); queue<int> qq; vi order; for (int i=1;i<=n;i++) if (!inc[i]) qq.push(i); while (!qq.empty()) { int f = qq.front(); order.push_back(f); gnomes[f].insert({0,f}); gotgnomes[f].insert({f,0}); qq.pop(); for (auto it : egdes[f]) { for (auto itt : gnomes[it]) { auto ittt = gotgnomes[f].lower_bound({itt.second,0}); if (ittt->first == itt.second) { if (ittt->second >= itt.first+1) continue; gnomes[f].erase({ittt->second,itt.second}); gnomes[f].insert({itt.first+1,itt.second}); gotgnomes[f].erase(ittt); gotgnomes[f].insert({itt.second,itt.first+1}); } else { gnomes[f].insert({itt.first+1,itt.second}); gotgnomes[f].insert({itt.second,itt.first+1}); } if (gnomes[f].size() > B) gnomes[f].erase(gnomes[f].begin()); } } for (auto it : edges[f]) { if (!vis[it]) { inc[it]--; if (!inc[it]){ vis[it] = 1; qq.push(it); } } } } vi banned(n+1,0); while (q--) { int party,ban; cin >> party >> ban; vi bans(ban); for (int i=1;i<=ban;i++) { cin >> bans[i-1]; banned[bans[i-1]] = 1; } if (ban < B) { //Just check possible ones bool broken = 0; for (auto it = gnomes[party].rbegin();it != gnomes[party].rend();it++) { if (!banned[it->second]) { cout << it->first << '\n'; broken = 1; break; } } if (!broken) cout << -1 << '\n'; } else { //Do it again only sqrt(Y) can be like this vi dp(n+1,-inf); for (auto it : order) { if (!banned[it]) dp[it] = 0; for (auto itt : egdes[it]) dp[it] = max(dp[it],dp[itt]+1); } cout << (dp[party]<0?-1:dp[party]) << '\n'; } for (int i=1;i<=ban;i++) banned[bans[i-1]] = 0; } } signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifdef Local freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int t = 1; //cin >> t; while (t --> 0) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...