이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse3,avx2")
#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 = INT_MAX;
const ll MOD = (ll)1e9+7;
const ll B = 100;
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;
}
}
vector<ll> idp;
ll brute(ll u, set<ll> &block){
idp.assign(n+1, -1);
bdfs(u, idp, block);
return idp[u]==-INF?-1:idp[u];
}
vector<vector<pair<ll, ll>>> dp;
multiset<pair<ll, pair<ll, ll>>, greater<pair<ll, pair<ll, ll>>>> point;
void dfs(ll u, vector<bool> &vis){
vis[u]=1;
point.clear();
for (auto v:A[u]){
if (!vis[v]) dfs(v, vis);
for (auto ch:dp[v]) dp[u].push_back({ch.ff+1, ch.ss});
}
dp[u].push_back({0, u});
sort(dp[u].rbegin(), dp[u].rend());
while (dp[u].size()>B) dp[u].pop_back();
}
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);
}
// for (ll i=1; i<=n; i++){
// cout << i << ": ";
// for (auto v:dp[i]) cout << v.ff << "-" << v.ss << " ";
// cout << ln;
// }
set<ll> blocked;
while (q--){
ll t, y; cin >> t >> y;
blocked.clear();
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... |