Submission #1017409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017409		Ludissey	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2054 ms	506352 KiB

bitaro

//JAVAIS BESOIN DU HINT :(


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

using namespace std;

vector<pair<int,bool>> memo;
vector<bool> visited;
vector<vector<int>> neigh;
vector<vector<pair<int,int>>> minsqrt;
vector<bool> mp;
int timer=0;
int SQRT=0;
int mnDP2=0;

void dp(int x){
    if(visited[x]) return;
    visited[x]=true;
    unordered_map<int,bool> mp2;
    for (auto t : neigh[x]) {
        vector<pair<int,int>> nw;
        dp(t);
        int i=0;
        for (auto u : minsqrt[t])
        {
            if(mp2[u.second]==true) continue;
            if(sz(nw)==SQRT) break;
            while(sz(nw)<SQRT&&i<SQRT&&minsqrt[x][i].first>u.first+1) {
                nw.push_back(minsqrt[x][i]);
                if(minsqrt[x][i].second>=0) mp2[minsqrt[x][i].second]=true;
                if(sz(nw)==SQRT) break;
                i++;
            }
            if(sz(nw)==SQRT) break;
            if(u.second>=0) mp2[u.second]=true;
            nw.push_back({u.first+1,u.second});
        }
        while(sz(nw)<SQRT) {
            nw.push_back(minsqrt[x][i]);
            if(sz(nw)==SQRT) break;
            i++;
        }
        for (i = 0; i < SQRT; i++) minsqrt[x][i]={nw[i].first,nw[i].second};
    }
    vector<pair<int,int>> nw;
    bool b=false;
    for (int i = 0; i < SQRT; i++){
        if(!b&&0>minsqrt[x][i].first) {
            nw.push_back({0,x});
            b=true;
        }
        if(sz(nw)==SQRT) break;
        nw.push_back(minsqrt[x][i]);
        if(sz(nw)==SQRT) break;
    }
    for (int i = 0; i < SQRT; i++) 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);
    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);
    SQRT=sqrt(N);
    for (int i = 0; i < N; i++)
    {
        minsqrt[i].resize(SQRT,{-1e12,-1e12});
    }
    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);
    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=-1e12;
            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(-1LL,mnDP2) << "\n";
        }
        for (int i = 0; i < Y; i++)
        {
            mp[y[i]]=false;
        }
    }
    
    return 0;
}

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