Submission #1124948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124948		alecurse	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	2093 ms	2888 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>
#define mp make_pair
using namespace std;
vector<vector<int> > adj;
vector<vector<pair<int,int> > > bestofbest;
int root;
vector<bool> realvis;
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;
        }
    }   
    
    

}

int calcolarisposta(int x,unordered_set<int> &toer) {
    int maxres=0;
    for(auto b : adj[x]) {
        int ris= calcolarisposta(b,toer);
        if(toer.count(b)&&ris==0)
            continue;
        maxres=max(maxres,ris+1);
        
    }
    
    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 = 300;
    realvis.resize(N);
    bestofbest.resize(N,vector<pair<int,int> > (root,mp(-1,-1)));
    adj.resize(N);
    vis.resize(N);
    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++) {
        unordered_set<int> s;
           for(auto el : C[i]) {
            s.insert(el);
           }
        // if(Y[i]>root) {
           ans[i]=calcolarisposta(T[i],s);
           if(ans[i]==0&&s.count(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&&!s.count(bestofbest[T[i]][j].second)) {
        //             ans[i]=bestofbest[T[i]][j].first;
        //             break;
        //         }
        //     }
        //     if(ans[i]==0&&s.count(T[i])) {
        //         ans[i]=-1;
        //     }
        // }
    }
    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);
    
    assert(ans.size() == Q);
    for(int &x: ans) cout << x << "\n";
}

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