제출 #1017010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1017010		Ludissey	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	3 ms	1056 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<int> memo;
vector<bool> visited;
vector<vector<int>> neigh;
vector<vector<pair<int,int>>> minsqrt;
unordered_map<int,int> mp;
int timer=0;
int SQRT=0;
int mnDP2=0;

int dpinit(int x){
    if(memo[x]>=0) return memo[x];
    int mx=0;
    for (auto t : neigh[x]) {
        mx=max(mx,dpinit(t)+1);
    }
    memo[x]=mx;
    return mx;
}


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(i<SQRT&&minsqrt[x][i].first<=u.first) {
                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);
        }
        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&&memo[x]<minsqrt[x][i].first) {
            nw.push_back({memo[x],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;
}

int dp2(int x){
    int mx=0;
    for (auto u : neigh[x]) mx=max(mx,dp2(u)+1);
    if(!mp[x])  mnDP2=min(mnDP2,mx);
    return mx;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N,M,Q; cin >> N >> M >> Q;
    memo.resize(N,-1);        
    neigh.resize(N);
    visited.resize(N,false);
    minsqrt.resize(N);
    
    SQRT=sqrt(N);
    for (int i = 0; i < N; i++)
    {
        minsqrt[i].resize(SQRT,{1e9,-1e9});
    }
    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++)
    {
       if(leaf[i]) dpinit(i);
    }
    for (int i = 0; i < N; i++)
    {
       if(leaf[i]) dp(i);
    }
    while (Q--)
    {
        int T,Y; cin >> T >> Y;
        T--;
        vector<int> y(Y);
        mp.clear();
        for (int i = 0; i < Y; i++)
        {
            cin >> y[i];
            y[i]--;
            mp[y[i]]=true;
        }
        if(Y>=SQRT){
            mnDP2=1e9;
            int d=dp2(T);
            cout << max(-1LL,d-mnDP2) << "\n";
        }else{
            visited.clear();
            visited.resize(N,false);
            mnDP2=1e9;
            for (int i = 0; i < SQRT; i++)
            {
                if(minsqrt[T][i].second==1e9||mp[minsqrt[T][i].second]) continue;
                mnDP2=min(minsqrt[T][i].first,mnDP2);
            }
            int d=memo[T];
            cout << max(-1LL,d-mnDP2) << "\n";
            
        }

    }
    
    return 0;
}

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