Submission #1017942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017942		Ludissey	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1584 ms	141992 KiB

bitaro

//JAVAIS BESOIN DU HINT :(


#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define last(a) a[sz(a)-1]

using namespace std;
using namespace std::chrono;

vector<pair<int,bool>> memo;
vector<bool> visited;
vector<vector<int>> neigh;
vector<vector<pair<int,int>>> minsqrt;
vector<bool> mp;
vector<bool> mp2;
int timer=0;
int SQRT=0;
int mnDP2=0;
int c=0;
void dp(int x){
    if(visited[x]) return;
    visited[x]=true;
    minsqrt[x][0]={0,x};
    for (auto t : neigh[x]) {
        vector<pair<int,int>> nw;
        dp(t);
        int i=0;
        int j=0;
        while(sz(nw)<SQRT&&(i<SQRT||j<SQRT)){
            if(i<SQRT&&minsqrt[x][i].second>=0&&mp2[minsqrt[x][i].second]) {
                i++;
                continue;
            }
            if(j<SQRT&&minsqrt[t][j].second>=0&&mp2[minsqrt[t][j].second]) {
                j++;
                continue;
            }
            if(i<SQRT&&minsqrt[x][i].first>minsqrt[t][j].first+1){
                if(minsqrt[x][i].second>=0) mp2[minsqrt[x][i].second]=true;
                nw.push_back(minsqrt[x][i]);
                i++;
            }else{
                if(minsqrt[t][j].second>=0) mp2[minsqrt[t][j].second]=true;
                nw.push_back({minsqrt[t][j].first+1,minsqrt[t][j].second});
                j++;
            }
        }
        for (i = 0; i < SQRT; i++) { 
            if(nw[i].second>=0) mp2[nw[i].second]=false; 
            minsqrt[x][i]={nw[i].first,nw[i].second}; 
        }
    }
    return;
}

pair<int,bool> dp2(int x){
    if(memo[x].first>=0) return memo[x];
    int mx=0;
    bool b=!(mp[x]);
    for (auto t : neigh[x]) {
        pair<int,bool> d=dp2(t);
        if(d.second==false) continue;
        b=true;
        mx=max(mx,d.first+1);
    }
    memo[x]={mx,b};
    return {mx,b};
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); 
    //auto start = high_resolution_clock::now();
    int N,M,Q; cin >> N >> M >> Q;
    memo.resize(N,{-1,false});        
    neigh.resize(N);
    visited.resize(N,false);
    minsqrt.resize(N);
    mp.resize(N);
    mp2.resize(N,false);
    SQRT=sqrt(N)/2;
    for (int i = 0; i < N; i++)
    {
        minsqrt[i].resize(SQRT+1,{-1e9,-1e9});
    }
    c=0;
    vector<bool> leaf(N,true);
    for (int i = 0; i < M; i++)
    {
        int a,b; cin >> a >> b;
        a--; b--;
        neigh[b].push_back(a);
        leaf[a]=false;
    }
    for (int i = 0; i < N; i++) dp(i);
    //cout << c << "\n";
    while (Q--)
    {
        int T,Y; cin >> T >> Y;
        T--;
        vector<int> y(Y);
        for (int i = 0; i < Y; i++)
        {
            cin >> y[i];
            y[i]--;
            mp[y[i]]=true;
        }
        if(Y>=SQRT){
            memo.clear();
            memo.resize(N,{-1,false});
            pair<int,bool> d=dp2(T);
            if(d.second==false) d.first=-1;
            cout << d.first << "\n";
        }else{
            mnDP2=-1e9;
            for (int i = 0; i < SQRT; i++)
            {
                if(minsqrt[T][i].second<0||mp[minsqrt[T][i].second]) continue;
                mnDP2=max(minsqrt[T][i].first,mnDP2);
            }
            cout << max(-1,mnDP2) << "\n";
        }
        for (int i = 0; i < Y; i++)
        {
            mp[y[i]]=false;
        }
    }
    /*auto stop = high_resolution_clock::now();
    auto duration = duration_cast<seconds>(stop - start);
    cout << duration.count() << "s\n";*/
    return 0;
}

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