Submission #1160447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160447		theSkeleton	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2092 ms	14120 KiB

bitaro

//!!in the name of god!!
#include<bits/stdc++.h>
#define space <<' '<<
#define endl '\n'
#define inf 1e14
#define F first
#define S second
#define PB push_back
#define PF push_front
#define pll pair<ll,ll>
#define pii pair<int,int>
#define md(a) ((a+mod)%mod)
#define MP(a,b) make_pair(a,b)
#define all(a) a.begin(),a.end()
#define MT(a,b,c) make_tuple(a,b,c)
#define has(a,b) (a.find(b)!=a.end())
typedef long long ll;
using namespace std;
template<typename t> using heap=
priority_queue<t,vector<t>,greater<t>>;
const int mx = 1e5+5;
const int sq = 300;

vector<pii> ans[mx];
vector<int> adj[mx];
vector<int> tmp[mx];
int cnt[mx];


bool avb[mx];
int dp[mx];
int n,m,q;

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse4")

inline int solve(int e){
    for(int i=1;i<=e;i++){
        if(avb[i]){
            dp[i]=0;
        }
        else{
            dp[i]=-n*2;
        }
        for(int u:adj[i]){
            dp[i]=max(dp[i],dp[u]+1);
        }
    }
    return (0<=dp[e]?dp[e]:-1);
}

bool bad[mx];

int main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>q;
    for(int u,v;m--;){
        cin>>u>>v;
        adj[v].PB(u);
        tmp[u].PB(v);
        cnt[v]++;
    }
    vector<int> lst;
    for(int i=1;i<=n;i++){
        if(cnt[i]==0){
            lst.PB(i);
        }
    }
    while(!lst.empty()){
        int c=lst.back();
        lst.pop_back();
        for(int u:tmp[c]){
            cnt[u]--;
            if(cnt[u]==0){
                lst.push_back(u);
            }
        }
        vector<pii> arr;
        arr.PB(MP(0,c));
        for(int u:adj[c]){
            for(auto d:ans[u]){
                arr.PB(MP(d.F+1,d.S));
            }
        }
        sort(all(arr));
        reverse(all(arr));
        for(int i=0;i<arr.size()&&ans[c].size()<sq;i++){
            if(!bad[arr[i].S]){
                bad[arr[i].S]=1;
                ans[c].PB(arr[i]);
            }
        }
        for(pii d:ans[c]){
            bad[d.S]=0;
        }
    }
    vector<int> rmv;
    fill(avb,avb+n+1,1);
    for(int e,c;q--;){
        cin>>e>>c;
        if(c<sq){
            for(int i;c--;){
                cin>>i;
                bad[i]=1;
                rmv.PB(i);
            }
            int o=-1;
            for(auto d:ans[e]){
                if(!bad[d.S]){
                    o=d.F;
                    break;
                }
            }
            for(int i:rmv){
                bad[i]=0;
            }
            rmv.clear();
            cout<<o<<endl;
        }
        else{
            //fill(avb,avb+n+1,1)
            for(int i;c--;){
                cin>>i;
                avb[i]=0;
                rmv.PB(i);
            }
            cout<<solve(e)<<endl;
            for(int i:rmv){
                avb[i]=1;
            }
            rmv.clear();
        }
    }
    return 0;
}

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