이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
using namespace std;
const ll INF = 2e18;
const ll MOD = (ll)1e9+7;
const ll B = 200;
ll n, m, q;
vector<vector<ll>> A;
void bdfs(ll u, vector<ll> &dp, set<ll> &blocked){
dp[u]=0;
for (auto v:A[u]){
if (dp[v]==-1){
bdfs(v, dp, blocked);
}
dp[u]=max(dp[u], dp[v]+1);
}
if (dp[u]==0 and blocked.count(u)){
dp[u]=-INF;
}
}
ll brute(ll u, set<ll> &block){
vector<ll> dp(n+1, -1);
bdfs(u, dp, block);
return dp[u]==-INF?-1:dp[u];
}
vector<vector<pair<ll, ll>>> dp;
void append(pair<ll, ll> x, vector<pair<ll, ll>> &st){
st.push_back(x);
}
void dfs(ll u, vector<bool> &vis){
vis[u]=1;
for (auto v:A[u]){
if (!vis[v]) dfs(v, vis);
for (auto ch:dp[v]){
append({ch.ff+1, ch.ss}, dp[u]);
}
}
append({0, u}, dp[u]);
sort(dp[u].rbegin(), dp[u].rend());
while (dp[u].size()>B) dp[u].pop_back();
reverse(dp[u].begin(), dp[u].end());
}
void solve(){
cin >> n >> m >> q;
A.resize(n+1);
for (ll i=0; i<m; i++){
ll u, v; cin >> u >> v;
A[v].push_back(u);
}
dp.resize(n+1);
vector<bool> vis(n+1);
for (ll i=1; i<=n; i++){
if (!vis[i]) dfs(i, vis);
}
while (q--){
ll t, y; cin >> t >> y;
set<ll> blocked;
for (ll i=0; i<y; i++){
ll x; cin >> x; blocked.insert(x);
}
if (y<B){
ll mx=-1;
for (auto ch:dp[t]){
if (!blocked.count(ch.ss)) mx=max(mx, ch.ff);
}
cout << mx << ln;
}else{
cout << brute(t, blocked) << ln;
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
ll t=1;
// cin >> t;
while (t--) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |