Submission #1043658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043658		khanhtb	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1310 ms	415576 KiB

bitaro

// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define fi first
#define se second
using namespace std;
const ll mod = 998244353; 
const ll inf = 2e18;
const ll B = 320;
const ll N = 1e5+8;
int n,m,Q;
vector<int> g[N];
vector<pair<int,int>> best[N];
int d[N],vst[N],bad[N],dp[N];
void solve(){
    cin >> n >> m >> Q;
    for(int i = 1; i <= m; i++){
        int u,v;cin >> u >> v;
        g[v].pb(u);
    }
    for(int u = 1; u <= n; u++){
        vector<int> cur;
        for(int v:g[u]){
            for(pair<int,int> ed:best[v]){
                int vv = ed.se, w = ed.fi;
                if(vst[vv] == u) d[vv] = max(d[vv],w+1);
                else{
                    vst[vv] = u;
                    d[vv] = w+1;
                    cur.pb(vv);
                }
            }
        }
        for(int v:cur) best[u].pb({d[v],v});    
        best[u].pb({0,u});
        sort(all(best[u]),greater<pair<int,int>>());
        while(best[u].size() > B) best[u].pop_back();
    }
    for(int q = 1; q <= Q; q++){
        int t,s;cin >> t >> s;
        for(int i = 1; i <= s; i++){
            int x;cin >> x;
            bad[x] = q;
        }
        int ans = -1;
        if(s < B){
            for(pair<int,int> v:best[t]){
                if(bad[v.se] != q){
                    ans = v.fi;
                    break;
                }
            }
        }
        else{
            fill(dp,dp+n+1,-1);
            for(int u = 1;  u <= t; u++){
                if(bad[u] != q) dp[u] = 0;
                for(int v:g[u]){
                    if(dp[v] != -1) dp[u] = max(dp[u],dp[v]+1);
                }
            }
            ans = dp[t];
        }
        cout << ans << '\n';
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // if (fopen("test.inp", "r")) {
    //     freopen("test.inp", "r", stdin);
    //     freopen("test.out", "w", stdout);
    // }   
    ll T = 1;
    // cin >> T;
    for (ll i = 1; i <= T; i++) {
        solve();
        cout << '\n';
    }
}

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