제출 #1354679

#제출 시각아이디문제언어결과실행 시간메모리
1354679HossamHero7Bitaro’s Party (JOI18_bitaro)C++20
100 / 100
1118 ms432984 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 1e5 + 5 , B = 320;
vector<int> adj[N];
vector<pair<int,int>> dp[N];
bool vis[N];
void solve(int node){
    if(dp[node].size()) return;
    for(auto ch : adj[node]) solve(ch);
    priority_queue<array<int,3>> q;
    for(auto ch : adj[node]){
        q.push({dp[ch][0].first+1,ch,0});
    }
    vis[node] = 1;
    while(q.size() && dp[node].size() <= B){
        auto [_,ch,idx] = q.top();          q.pop();
        if(vis[dp[ch][idx].second]) goto gt;
        dp[node].push_back({_,dp[ch][idx].second});
        vis[dp[ch][idx].second] = 1;
        gt:
        if(idx + 1 < (int)dp[ch].size()) q.push({dp[ch][idx+1].first+1,ch,idx+1});
    }
    dp[node].push_back({0,node});
    for(auto [_,x] : dp[node]) vis[x] = 0;
}
bool mark[N];
int dp2[N];
int solve2(int node){
    int &ret = dp2[node];
    if(ret != -1) return dp2[node];
    ret = (mark[node] ? -1e9 : 0);
    for(auto ch : adj[node]){
        ret = max(ret , solve2(ch) + 1);
    }
    return ret;
}
void solve(){
    int n,m,q;
    cin>>n>>m>>q;
    vector<int> deg(n+1);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        deg[a] ++;
        adj[b].push_back(a);
    }
    for(int i=1;i<=n;i++){
        if(deg[i]) continue;
        solve(i);
    }
    while(q--){
        int node,sz;
        cin>>node>>sz;
        vector<int> v(sz);
        for(auto &i:v) cin>>i;
        if(sz <= B){
            for(auto i : v) mark[i] = 1;
            for(auto [d,x] : dp[node]){
                if(mark[x]) continue;
                cout<<d<<endl;
                goto gt;
            }
            cout<<-1<<endl;
            gt:
            for(auto i : v) mark[i] = 0;
        }
        else {
            memset(dp2,-1,sizeof(dp2));
            for(auto i : v) mark[i] = 1;
            cout<<(solve2(node)<0?-1:solve2(node))<<endl;
            for(auto i : v) mark[i] = 0;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…