Submission #1321982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321982		Sofiatpc	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	2058 ms	222036 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
const int MAXN = 1e5+5;
vector<int> adj[MAXN], radj[MAXN], ini[MAXN], dist[MAXN];
int mx[MAXN], marc[MAXN], val[MAXN], g[MAXN], in[MAXN];

bool cmp(int a, int b){
    return mx[a] > mx[b];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int B = 158;

    int n,m,q; cin>>n>>m>>q;
    for(int i = 1; i <= m; i++){
        int a,b; cin>>a>>b;
        adj[a].push_back(b); in[b] ++;
        radj[b].push_back(a);   
    }

    for(int i = 1; i <= n; i++){
        vector<int> v;

        for(int viz : radj[i]){
            for(int j = 0; j < sz(ini[viz]); j++){
                if(mx[ ini[viz][j] ] == 0){
                    mx[ ini[viz][j] ] = dist[viz][j] + 1;
                    v.push_back( ini[viz][j] );
                }else{
                    mx[ ini[viz][j] ] = max( mx[ ini[viz][j] ], dist[viz][j] + 1);
                }
            }
        }

        sort(v.begin(),v.end(),cmp);

        for(int j = 0; j < sz(v); j++){
            if(mx[v[j]] == 0)break;
            if(j < B){ ini[i].push_back(v[j]); dist[i].push_back( mx[v[j]] ); }
            mx[v[j]] = 0;
        }
        ini[i].push_back( i ); dist[i].push_back( 0 );
    }

    for(int id = 1; id <= q; id++){
        int v, qtd; cin>>v>>qtd;
        vector<int> block;
        for(int i = 0; i < qtd; i++){
            int x; cin>>x;
            block.push_back(x);
            marc[x] = 1;
        }

        if(qtd >= B){
            queue<int> q; 
            for(int i = 1; i <= n; i++){
                val[i] = -1; g[i] = in[i];
                if(in[i] == 0){
                    q.push(i); 
                    val[i] = (marc[i]) ? -1 : 0;
                }
            }
                
            while(!q.empty()){
                int x = q.front(); q.pop();
                if(!marc[x])val[x] = max(val[x], 0);

                for(int viz : adj[x]){
                    if(val[x] != -1)val[viz] = max(val[viz], val[x]+1);
                    g[viz]--;

                    if(g[viz] == 0)q.push(viz);
                }
            }
            cout<<val[v]<<"\n";
        }else{
            int ok = 0;
            for(int i = 0; i < sz(dist[v]); i++)
                if(!marc[ ini[v][i] ]){ok = 1; cout<<dist[v][i]<<"\n"; break; }
            
            if(!ok)cout<<"-1\n";
        }

        for(int x : block)marc[x] = 0;
    }
}

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