Submission #1103442

#TimeUsernameProblemLanguageResultExecution timeMemory
1103442danglayloi1Bitaro’s Party (JOI18_bitaro)C++17
0 / 100
4 ms5968 KiB
#include <bits/stdc++.h> #define ii pair<int, int> #define fi first #define se second #define inf 0x3f3f3f3f3f3f3f3f using namespace std; const int nx=1e5+5; const int bl=317; int n, m, q, tmp[nx], d[nx]; vector<int> adj[nx]; vector<ii> best[nx]; bool ok[nx]; queue<int> f; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>q; while(m--) { int u, v; cin>>u>>v; adj[v].emplace_back(u); } memset(tmp, -1, sizeof(tmp)); for(int u = 1; u <= n; u++) { vector<int> cur; best[u].emplace_back(0, u); for(int v:adj[u]) { for(auto it:best[v]) { int c=it.se, w=it.fi; if(tmp[c]==-1) tmp[c]=w+1, cur.emplace_back(c); else tmp[c]=max(tmp[c], w+1); } } for(int v:cur) { best[u].emplace_back(tmp[v], v); tmp[v]=-1; } sort(best[u].begin(), best[u].end(), greater<ii>()); while(best[u].size()>bl) best[u].pop_back(); } while(q--) { int t, y, ans=-1; vector<int> a; cin>>t>>y; a.resize(y); for(int i = 0; i < y; i++) cin>>a[i], ok[a[i]]=1; if(y<bl) { for(auto it:best[t]) { if(ok[it.se]) continue; ans=it.fi; break; } } else { for(int i = 1; i <= n; i++) d[i]=-1; d[t]=0; f.push(t); while(f.size()) { int u=f.front(); f.pop(); for(int v:adj[u]) if(d[v]==-1) d[v]=d[u]+1, f.push(v); } for(int i = 1; i <= n; i++) if(d[i]!=-1 && !ok[i]) ans=max(ans, d[i]); } for(int i = 0; i < y; i++) ok[a[i]]=0; cout<<ans<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...