Submission #1124895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124895		alecurse	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	1 ms	320 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>
using namespace std;
vector<vector<int> > adj;
vector<set<pair<int,int> > > bestofbest;
int root;
vector<bool> vis;
void dfs(int x) {
    
    if(vis[x]) return;
    vis[x]=true;
    for(auto b : adj[x]) {
        dfs(b);
        for(auto el : bestofbest[b]) {
           
            bestofbest[x].insert(make_pair(el.first+1,el.second));
            if(bestofbest[x].size()>root) {
                bestofbest[x].erase(bestofbest[x].begin());
            }
        }
        bestofbest[x].insert(make_pair(1,b));
        if(bestofbest[x].size()>root) {
            bestofbest[x].erase(bestofbest[x].begin());
        }
    }

}

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 = sqrt(N);
    bestofbest.resize(N);
    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);
    }
    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);
        } else {
            auto it = bestofbest[T[i]].end();
            while(it!=bestofbest[T[i]].begin()) {
                it=prev(it,1);
                if(!s.count((*it).second)) {
                    ans[i]=(*it).first;
                    break;
                }
            }
            if(ans[i]==0) {
                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