Submission #963270

#	Time	Username	Problem	Language	Result	Execution time	Memory
963270		TimAni	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1735 ms	214760 KiB

bitaro

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cmath>
#include <stack>
#include <set>
#include <functional>
#include <bitset>
#include <map>
#include <unordered_map>
#include <queue>
#include <array>
#include <numeric>
#include <complex>
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename A> ostream& operator<<(ostream& os, vector<A>& a) { for(auto &c:a)os<<c<<' '; return os;}
template<typename A> istream& operator>>(istream& os, vector<A>& a) { for(auto &c:a)os>>c; return os;}
template<typename A,size_t N> istream& operator>>(istream &os, array<A,N>&a) { for(auto &c:a)os>>c; return os;}
template<typename A,typename B> istream& operator>>(istream& os, pair<A,B>&a) { os>>a.first>>a.second; return os;}
template<typename A> istream& operator >>(istream& os,complex<A>& a){pair<A,A>aux;os>>aux;a=complex<A>(aux.first,aux.second);return os;}
#define bug(a) cerr << "(" << #a << ": " << a << ")\n";
#define all(x) x.begin(),x.end()
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define PQ priority_queue
#define x real
#define y imag
using pii= pair<int,int>;
using VI= vector<int>;
using v64= vector<int64_t>;
using point=complex<double>;
using i64= int64_t;
using i16= int16_t;
using u64= uint64_t;
using u32= uint32_t;
using i32= int32_t;
using u16= uint16_t;
const i32 inf=1e9;
const i64 INF=1e18;
const int mod=1e9+7;
const int sigma=26;
void solve()
{
    int n,m,q;
    cin>>n>>m>>q;
    const int sq=150;//int(sqrt(n));
    vector<vector<int>>g(n);
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        g[y-1].pb(x-1);
    }
    vector<vector<pii>>best(n);
    vector<int>val(n,-1);
    //(m+n) * sq *log(sq*(m+n))
    for(int i=0;i<n;i++)
    {
        vector<int>aux;
        aux.pb(i);
        val[i]=0;
        for(auto &v:g[i])
        {
            for(auto &c:best[v])
            {
                aux.pb(c.first);
                val[c.first]=max(val[c.first],c.second+1);
            }
        }
        sort(all(aux));
        aux.erase(unique(all(aux)),aux.end());
        sort(all(aux),[&](int x,int y){
            return val[x]>val[y];
        });
        for(auto &c:aux)
        {
            if(best[i].size()<sq)
                best[i].pb({c,val[c]});
            val[c]=-1;
        }
    }
    vector<bool>viz(n,0);
    while(q--)
    {
        int x,cnt;
        cin>>x>>cnt;
        x--;
        vector<int>a(cnt);
        cin>>a;
        for(auto &c:a)
            c--;
        for(auto &c:a)
            viz[c]=true;
        int rez=-1;
        if(cnt<sq)
        {
            for(auto &c:best[x])
            {
                if(!viz[c.first])
                    rez=max(rez,c.second);
            }
        }
        else
        {
            vector<int>dp(x+1,-inf);
            for(int i=0;i<=x;i++)
            {
                if(!viz[i])
                    dp[i]=0;
                for(auto &c:g[i])
                {
                    dp[i]=max(dp[i],dp[c]+1);
                }
            }
            rez=max(dp[x],-1);
        }
        cout<<rez<<'\n';
        for(auto &c:a)
            viz[c]=false;
 
    }
 
}
main()
{
    i32 tt=1;
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cin>>tt;
    while(tt--)
    {
        solve();
    }
}

Compilation message (stderr)

bitaro.cpp:128:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  128 | main()
      | ^~~~

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