Submission #56809

#	Time	Username	Problem	Language	Result	Execution time	Memory
56809		Diuven	Bitaro’s Party (JOI18_bitaro)	C++11	14 / 100	2045 ms	289760 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, inf=2e9, BMX=350;

int n, m, q, b=300;
vector<int> G1[MX], G2[MX];

bool used[MX];
struct bucket {
    pii X[BMX];
    bucket(){
        for(int i=1; i<BMX; i++)
            X[i]={-inf, 0};
    }
    bucket operator + (const bucket& A) const {
        bucket res;
        for(int i=1, p1=1, p2=1; i<=b; i++){
            while(p1<=b && used[X[p1].second]) p1++;
            while(p2<=b && used[A.X[p2].second]) p2++;
            if(p1>b) res.X[i]=A.X[p2++];
            else if(p2>b) res.X[i]=X[p1++];
            else if(X[p1]<A.X[p2]) res.X[i]=A.X[p2++];
            else res.X[i]=X[p1++];
            if(res.X[i].second>0) used[res.X[i].second]=true;
        }
        for(int i=1; i<=b; i++)
            used[res.X[i].second]=false;
        return res;
    }
} V[MX];

bool vis[MX];
void dfs1(int v){
    V[v].X[1]={-1,v};
    vis[v]=true;
    for(int x:G2[v]){
        if(!vis[x]) dfs1(x);
        V[v]=V[v]+V[x];
    }
    for(int i=1; i<=b; i++) V[v].X[i].first++;
}

int D[MX];
bool out[MX];
int dfs2(int v){
    int &res=D[v];
    if(res!=-1) return res;
    res = (out[v] ? -inf : 0);
    for(int x:G2[v]){
        res=max(res, dfs2(x)+1);
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1; i<=m; i++){
        int u, v; cin>>u>>v;
        G1[u].push_back(v);
        G2[v].push_back(u);
    }
    for(int i=1; i<=n; i++) if(!vis[i]) dfs1(i);

    for(int i=1; i<=q; i++){
        int v, x; cin>>v>>x;
        vector<int> A;
        for(int i=1; i<=x; i++){
            int a; cin>>a;
            A.push_back(a);
            out[a]=true;
        }
        int ans=-1;
        if(x>=b){
            fill(D, D+n+1, -1);
            ans=max(ans, dfs2(v));
        }
        else{
            pii *P=V[v].X;
            for(int i=1; i<=b; i++){
                if(!out[P[i].second]){
                    ans=max(ans, P[i].first);
                    break;
                }
            }
        }
        cout<<ans<<'\n';
        for(int a:A) out[a]=false;
    }
    
    return 0;
}

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