Submission #1321985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321985		Sofiatpc	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	977 ms	215388 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;


#define sz(v) (int)v.size()
const int MAXN = 1e5+5;
vector<int> radj[MAXN], ini[MAXN], dist[MAXN];
int mx[MAXN], marc[MAXN], val[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;
        radj[b].push_back(a);   
    }

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

        for(int k = 0; k < sz(radj[i]); k++){
            for(int j = 0; j < sz(ini[radj[i][k]]); j++){
                if(mx[ ini[radj[i][k]][j] ] == 0){
                    mx[ ini[radj[i][k]][j] ] = dist[radj[i][k]][j] + 1;
                    v.push_back( ini[radj[i][k]][j] );
                }else{
                    mx[ ini[radj[i][k]][j] ] = max( mx[ ini[radj[i][k]][j] ], dist[radj[i][k]][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(qtd);
        for(int i = 0; i < qtd; i++){
            cin>>block[i];
            marc[block[i]] = 1;
        }

        if(qtd >= B){
            for(int i = 1; i <= n; i++){
                val[i] = -1;
                if(!marc[i])val[i] = 0;
                for(int viz : radj[i])
                    if(val[viz] != -1)val[i] = max(val[i], val[viz]+1);
            }
            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 i = 0; i < qtd; i++)marc[block[i]] = 0;
    }
}

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