Submission #1321977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321977		Sofiatpc	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	3 ms	824 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

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

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

        for(int viz : adj[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 < B; j++){
            if(mx[v[j]] == 0 && v[j] != i)break;
            ini[i].push_back(v[j]); dist[i].push_back( mx[v[j]] );
            mx[v[j]] = 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; q.push(v);
            val[v] = 0;

            int mx = 0;
            while(!q.empty()){
                int x = q.front(); q.pop();
                mx = max(mx, val[x]);

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

                    if(g[viz] == 0)q.push(viz);
                }
            }
            cout<<mx<<"\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: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86