Submission #862663

#	Time	Username	Problem	Language	Result	Execution time	Memory
862663		mraron	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1323 ms	467684 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=344;
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();
        best[i].shrink_to_fit();
        
        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;
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) {
                dp[j]=-1;
            }
            
            ans=-1;
            dp[t]=0;
            for(int i=t;i>=1;i--) {
                if(!blocked[i]) ans=max(ans, dp[i]);
                if(dp[i]!=-1) {
                    for(int j:badj[i]) {
                        dp[j]=max(dp[j], dp[i]+1);
                    }
                }
            }
            cout<<ans<<"\n";
        }
        
        for(int j:y) blocked[j]=0;
    }
}

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