Submission #419359

#	Time	Username	Problem	Language	Result	Execution time	Memory
419359		Malheiros	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1702 ms	61324 KiB

bitaro

#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+10;
const int magic=50;
int n;
vector<pii> dists[maxn];
 
vector<int> rev[maxn];
int ids[maxn];

bool vistos[maxn];
void merge(int ind){
    priority_queue<pair<pii,int>> heap;
    heap.push({{0,ind},-1});
    for (auto k:rev[ind]){
        heap.push({{dists[k][0].first+1,dists[k][0].second},k});
        ids[k]++;
    }
    vector<int>curon;
    while(!heap.empty() && dists[ind].size()<magic){
        auto o=heap.top();
        if (vistos[o.FS]==0){
            dists[ind].PB(o.first);
            vistos[o.FS]=1;
            curon.PB(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:curon) vistos[k]=0; 
    for (auto k:rev[ind])ids[k]=0;
    
}
 
bool onlines[maxn];
int solve(int a){
    
    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 (onlines[i]==0 && 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;
        vector<int>curon;
        while(a--){
            int b;cin>>b;
            onlines[b]=1;
            curon.PB(b);
        }
        bool ach=false;
        for (auto k:dists[t]){
            if (onlines[k.second]==0){
                ach=true;
                cout<<k.first<<'\n';
                break;
            }
        }
        if (!ach){
           //cout<<-1<<endl;
            cout<<solve(t)<<'\n';
        }
        for (auto k:curon){
            onlines[k]=0;
        }
    }
 
}

Compilation message (stderr)

bitaro.cpp: In function 'void merge(int)':
bitaro.cpp:61: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]
   61 |         if (idx>0 && ids[idx]<dists[idx].size()){
      |                      ~~~~~~~~^~~~~~~~~~~~~~~~~~

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