Submission #347269

#	Time	Username	Problem	Language	Result	Execution time	Memory
347269		ewwdsgfvsd	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	4 ms	5120 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=300;
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;
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({-1,i});
        for(ll j : adj[i]){
            for(pll p : d[j])
                d[i].pb({p.F-1,p.S});
            sort(d[i].begin(),d[i].end());
            d[i].resize(SQ);
        }
    }
    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-1 << '\n';
                    break;
                }
        }else{
            ll f[N];
            for(ll i=1; i<=n; i++){
                if(t.find(i)==t.end()){
                    f[i]=1;
                }else f[i]=0;
                for(ll j : adj[i]) f[i]=max(f[i],f[j]+1);
            }
            cout << f[v]-1 << '\n';
        }
    }
    return 0;
}

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