Submission #1124995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124995		alecurse	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2104 ms	231904 KiB

bitaro

#include <iostream>
#include <vector>
#include <cassert>
#include <vector>
#include <math.h>
#include <limits.h>
#include <set>
#include <limits.h>
#include <unordered_set>
#include <iostream>
#include <unordered_map>
#define mp make_pair
using namespace std;
vector<vector<int> > adj;
vector<vector<pair<int,int> > > bestofbest;
int root;
vector<bool> realvis;
 vector<bool> isin;
vector<bool> vis;
void dfs(int x) {
    
    if(vis[x]) return;
    vis[x]=true;
    for(auto b : adj[x]) {
        dfs(b);
    }

    vector<int> indici(adj[x].size());

    for(auto b : adj[x]) {
        for(int i=0;i<root;i++) {
            if(bestofbest[b][i].second!=-1) {
                realvis[bestofbest[b][i].second]=0;
            } else {
                break;
            }
        }
    }
    for(int i=0;i<root;i++) {
        int maxsf=-1;
        int maxfiglio=0;
        int realmaxfiglio=0;
        for(int j=0;j<adj[x].size();j++) {
            int b = adj[x][j];
            while(indici[j]<root&&bestofbest[b][indici[j]].second!=-1&&realvis[bestofbest[b][indici[j]].second]) {
                indici[j]++;
            }
            if(indici[j]>=root)
                continue;
            if(bestofbest[b][indici[j]].second==-1)
                continue;

            if(maxsf<=bestofbest[b][indici[j]].first+1) {
                
                maxsf=bestofbest[b][indici[j]].first+1;
                realmaxfiglio=bestofbest[b][indici[j]].second;
                maxfiglio=j;
            }
        }
        if(maxsf!=-1) {
            realvis[realmaxfiglio]=true;
            // alreadyadd.insert(realmaxfiglio);
            bestofbest[x][i]=make_pair(maxsf,realmaxfiglio);
            indici[maxfiglio]++;
        } else {
            bestofbest[x][i].first=0;
            bestofbest[x][i].second=x;
            break;
        }
    }   
    
    

}
// vector<int> resvis;
unordered_map<int,int> resvis;
int calcolarisposta(int x) {
    if(resvis.count(x))
        return resvis[x];
    int maxres=0;
    for(auto b : adj[x]) {
        int ris= calcolarisposta(b);
        if(isin[b]&&ris==0)
            continue;
        maxres=max(maxres,ris+1);
        
    }
    resvis[x]=maxres;
    return maxres;
} 

vector<int> uomoragno(int N, int M, int Q, vector<int> S, vector<int> E, vector<int> T, vector<int> Y, vector<vector<int> > C){
    vector<int> ans(Q); 
    root = 250;
    realvis.resize(N);
    bestofbest.resize(N,vector<pair<int,int> > (root,mp(-1,-1)));
    adj.resize(N);
    vis.resize(N);
    isin.resize(N+1);
    for(int i=0;i<M;i++) {
    
        adj[E[i]].push_back(S[i]);
    }
    for(int i=N-1;i>=0;i--) {
        dfs(i);
    }
    // cout<<"SUS\n";
    // for(int i=0;i<root;i++) {
    //     cout<<bestofbest[3][i].first<<" "<<bestofbest[3][i].second<<"\n";
    // }
    // cout<<"SUS\n";
   
    for(int i=0;i<Q;i++) {
           for(auto el : C[i]) {
            isin[el]=true;
           }
        if(Y[i]>=root) {
            resvis.clear();
           ans[i]=calcolarisposta(T[i]);
           if(ans[i]==0&&isin[T[i]]) {
            ans[i]=-1;
           }
        } else {
            for(int j=0;j<root;j++) {
                // cout<<bestofbest[T[i]][j].first<<"\n";
                if(bestofbest[T[i]][j].second!=-1&&!isin[bestofbest[T[i]][j].second]) {
                    ans[i]=bestofbest[T[i]][j].first;
                    break;
                }
            }
            if(ans[i]==0&&isin[T[i]]) {
                ans[i]=-1;
            }
        }
         for(auto el : C[i]) {
            isin[el]=false;
           }
    }
    return ans;
}

int main(){
    int N, M, Q;
    cin >> N >> M >> Q;

    vector<int> S(M), E(M);
    for(int i=0; i<M; i++){
        cin >> S[i] >> E[i];
        S[i]--;
        E[i]--;
    }

    vector<vector<int> > C(Q);
    vector<int> T(Q), Y(Q);
    for(int i=0; i<Q; i++){
        cin >> T[i] >> Y[i];
        T[i]--;
        C[i].resize(Y[i]);
        for(int j=0; j<Y[i]; j++){
            cin >> C[i][j];
            C[i][j]--;
        }
    }

    vector<int> ans = uomoragno(N, M, Q, S, E, T, Y, C);
    
    for(int i=0;i<ans.size();i++) {
        cout<<ans[i]<<"\n";
    }
}

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