Submission #347324

#	Time	Username	Problem	Language	Result	Execution time	Memory
347324		ewwdsgfvsd	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1805 ms	332524 KiB

bitaro

#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
/*#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")*/
using namespace std;
using ll = /*long long*/ int;
#define F first
#define S second
#define pb push_back
#define lc v<<1
#define rc 1+(v<<1)
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N=1e5+10,LN=20,M=1e5+10,SQ=250,inf=1e9;
const ll INF=1e18;
const int MOD=1000000007 /*998244353*/;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
    ll ans=1;
    while (y != 0) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
ll n,m,q;
bool g[N];
vector<pll> d[N];
vector<ll> adj[N];
int main(){
    fast_io;
    cin >> n >> m >> q;
    for(ll i=1; i<=m; i++){
        ll v,u;
        cin >> v >> u;
        adj[u].pb(v);
    }
    for(ll i=1; i<=n; i++){
        d[i].pb({0,i});
        ll k=1;
        for(ll j : adj[i]){
            for(pll p : d[j])
                d[i].pb({p.F-1,p.S});
            inplace_merge(d[i].begin(),d[i].begin()+k,d[i].end());
            vector<pll> v;
            for(pll p : d[i]) if(!g[p.S]) v.pb(p),g[p.S]=1;
            for(pll p : v) g[p.S]=0;
            swap(v,d[i]);
            k=d[i].size();
            k=min(k,SQ);
            d[i].resize(k);
        }
    }
    for(ll i=1; i<=n; i++) d[i].pb({1,0});
    while(q--){
        ll v,k;
        set<ll> t;
        cin >> v >> k;
        for(ll i=0; i<k; i++){
            ll u;
            cin >> u;
            t.insert(u);
        }
        if(k<SQ){
            for(pll p : d[v]){
                if(t.find(p.S)==t.end()){
                    cout << -p.F << '\n';
                    break;
                }
            }
        }else{
            ll f[v+1];
            for(ll i=1; i<=v; i++){
                if(t.find(i)==t.end()){
                    f[i]=0;
                }else f[i]=-1;
                for(ll j : adj[i]) if(f[j]!=-1) f[i]=max(f[i],f[j]+1);
            }
            cout << f[v] << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp:2: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    2 | #pragma comment(linker, "/stack:200000000")
      | 
bitaro.cpp:17:14: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   17 | const ll INF=1e18;
      |              ^~~~

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