제출 #862661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
862661		mraron	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	4 ms	9820 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;

const int MAXN=100001;

int n,m,q;
vector<int> adj[MAXN];
vector<int> badj[MAXN];

const int blksz=1001;
vector<pair<int,int>> best[MAXN];
int vis[MAXN], indeg[MAXN], volt[MAXN];
int currMark=0;
void dfs(int x) {
    vis[x]=1;
    for(auto& i:best[x]) i.first++;
    best[x].push_back({0, x});
    if(best[x].size()>blksz) best[x].resize(blksz);
    
    for(int i:adj[x]) {
        indeg[i]--;
        
        vector<pair<int,int>> res;
        res.resize(best[x].size()+best[i].size());
        merge(best[i].begin(), best[i].end(), best[x].begin(), best[x].end(), res.begin(), [&](auto& x, auto& y) -> bool {
            return x>y;
        });
        best[i].clear();
        
        currMark++;
        for(auto& j:res) {
            if(volt[j.second]!=currMark) {
                best[i].push_back(j);
                volt[j.second]=currMark;
            }
        }
        
        if(!indeg[i]) {
            dfs(i);
        }
    }
}

int blocked[MAXN];
int dp[MAXN];
int ans=0;
void topo(int x) {
    vis[x]=1;
    if(!blocked[x]) ans=max(ans, dp[x]);
    for(int i:badj[x]) {
        indeg[i]--;
        dp[i]=max(dp[i], dp[x]+1);
        if(0==indeg[i]) {
            topo(i);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>q;
    for(int i=0;i<m;++i) {
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        indeg[b]++;
        badj[b].push_back(a);
    }
    
    for(int i=1;i<=n;++i) if(!vis[i]) dfs(i);
    //~ for(int i=1;i<=n;++i) {
        //~ for(auto& [j,k]:best[i]) cerr<<j<<";"<<k<<" ";
        //~ cerr<<"\n";
    //~ }
    
    
    for(int i=0;i<q;++i) {
        int t,cnt;
        cin>>t>>cnt;
        vector<int> y(cnt);
        for(int& j:y) cin>>j;
        
        for(int j:y) blocked[j]=1;
        //~ cerr<<best[t].size()<<"!!\n";
        if((int)best[t].size()>cnt) {
            bool found=false;
            for(auto& j:best[t]) {
                if(!blocked[j.second]) {
                    cout<<j.first<<"\n";
                    found=true;
                    break ;
                }
            }
            if(!found) cout<<"-1\n";
        }else {
            for(int j=1;j<=n;++j) {
                indeg[j]=0;
            }
            for(int j=1;j<=n;++j) {
                vis[j]=0;
                dp[j]=0;
                for(int k:badj[j]) indeg[k]++;
            }
            
            ans=-1;
            topo(t);
            cout<<ans<<"\n";
        }
        
        for(int j:y) blocked[j]=0;
    }
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86