Submission #1017652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017652		Ludissey	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	869 ms	138448 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;
int timer=0;
int SQRT=0;
int mnDP2=0;
int c=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])
        {
            c++;
            //if(mp2[u.second]==true) continue;
            if(sz(nw)==SQRT) break;
            while(sz(nw)<SQRT&&i<SQRT&&minsqrt[x][i].first>u.first+1) {
                c++;
                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 < sz(nw); i++) { c++; 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); 
    //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);
    SQRT=sqrt(N)/2;
    for (int i = 0; i < N; i++)
    {
        minsqrt[i].resize(SQRT,{-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: 0 / 86