Submission #418664

#TimeUsernameProblemLanguageResultExecution timeMemory
418664MalheirosBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2071 ms9556 KiB
#include <bits/stdc++.h>
 
using namespace std;

#define ld long double
#define ll long long
//#define int ll
#define FF first.first
#define FS first.second
#define SF second.first
#define SS second.second
#define PB push_back
#define MP make_pair
#define all(cont) cont.begin(),cont.end()
#define rall(cont) cont.rbegin(), cont.rend()
#define FOR(i, j) for(int i=0;i<j;i++)
#define RFOR(i, j) for (int i=j;i>=0;i--)
#define GO cin.tie(NULL);
#define FAST ios_base::sync_with_stdio(false);
typedef pair<int,int> pii;
 


// Your function
//DEBBUGGING STUFF, JUST USE deb(a,b,c) and it will print the variables;
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cout << vars << " = ";
    string delim = "";
    (..., (cout << delim << values, delim = ", "));
    cout<<endl;
}

const int maxn=1e5;
const int magic=320;
int n;
vector<pii> dists[maxn];

vector<int> rev[maxn];
int ids[maxn];
void merge(int ind){
    priority_queue<pair<pii,int>> heap;
    heap.push({{0,ind},-1});
//    vector<int> ids(maxn,0);
    for (auto k:rev[ind]){
        heap.push({{dists[k][0].first+1,dists[k][0].second},k});
        ids[k]++;
    }
    unordered_set<int> vistos;
    while(!heap.empty() && dists[ind].size()<magic){
        auto o=heap.top();
        if (vistos.find(o.FS)==vistos.end()){
            dists[ind].PB(o.first);
            vistos.insert(o.FS);
        }
        heap.pop();
        auto idx=o.second;
        if (idx>0 && ids[idx]<dists[idx].size()){
            heap.push({{dists[idx][ids[idx]].first+1,dists[idx][ids[idx]].second},idx});
            ids[idx]++;
        }
    }
    for (auto k:rev[ind])ids[k]=0;
    
}

int solve(int a,unordered_set<int>& caras){
    
    vector<int>dp(a+1,-1);
    dp[a]=0;
    for(int i=a;i>=1;i--){
        if (dp[i]==-1) continue;
        for (auto k:rev[i]){
            dp[k]=max(1+dp[i],dp[k]);
        }
    }
    int maior=-1;
    for(int i=1;i<=a;i++){
        if (caras.find(i)==caras.end() && dp[i]!=-1){
            maior=max(maior,dp[i]);
        }
    }
    return maior;
}

int main(){
    GO FAST
    int m,q;
    cin>>n>>m>>q;
    FOR(i,m){
        int a,b;cin>>a>>b;
        rev[b].push_back(a);
    }
    for (int i=1;i<=n;i++){

        merge(i);
    }
   /* for (int i=1;i<=n;i++){
        cout<<i<<endl;
        for (auto k:dists[i]){
            cout<<k.first<<" : "<<k.second<<endl;
        }
        cout<<endl;
    }*/
    while(q--){
        int t;
        cin>>t;
        int a;
        cin>>a;
        unordered_set<int> caras;
        while(a--){
            int b;cin>>b;
            caras.insert(b);
        }
        bool ach=false;
        for (auto k:dists[t]){
            if (caras.find(k.second)==caras.end()){
                ach=true;
                cout<<k.first<<'\n';
                break;
            }
        }
        if (!ach){
           //cout<<-1<<endl;
            cout<<solve(t,caras)<<'\n';
        }
    }

}

Compilation message (stderr)

bitaro.cpp: In function 'void merge(int)':
bitaro.cpp:59:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         if (idx>0 && ids[idx]<dists[idx].size()){
      |                      ~~~~~~~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...