Submission #480442

#	Time	Username	Problem	Language	Result	Execution time	Memory
480442		MohammadAghil	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1641 ms	118992 KiB

bitaro

#include <bits/stdc++.h> 
using  namespace std;
typedef  long long ll;
typedef  pair<int, int> pp;
#define  rep(i,l,r) for(int i = (l); i < r; i++)
#define  per(i,r,l) for(int i = (r); i >= l; i--)
#define  all(x) x.begin(), x.end()
#define  sz(x) (int)(x).size()
#define  pb push_back
#define  ff first
#define  ss second 

const ll mod = 1e9 + 7, maxn = 2e5 + 5, maxlg = 21, inf = 1e9 + 5;

int sq = 100;
vector<int> adj[maxn];
vector<pp> best[maxn];
bool is[maxn];

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    int n, m, q; cin >> n >> m >> q;
    rep(i,0,m){
        int u, v; cin >> u >> v;
        u--, v--;
        adj[v].pb(u);
    }
    rep(i,0,n){
        vector<pp> a;
        a.pb(pp(-1, i));
        for(int r: adj[i]){
            for(pp c: best[r]){
                a.pb(c);
            }
        }
        sort(all(a));
        reverse(all(a));
        for(pp c: a){
            if(!is[c.ss]){
                is[c.ss] = true;
                c.ff++;
                best[i].pb(c);
            }
            if(sz(best[i]) == sq) break;
        }
        for(pp c: best[i]) is[c.ss] = false;
    }
    while(q--){
        int t, c; cin >> t >> c;
        vector<int> city;
        rep(i,0,c){
            int r; cin >> r; r--;
            city.pb(r);
            is[r] = true;
        }
        if(c < sq){
            for(auto p: best[t - 1]){
                if(!is[p.ss]){
                    cout << p.ff << '\n';
                    goto hell;
                }
            }
            cout << -1 << '\n';
            hell:;
        }else{
            vector<int> dp(t, -inf);
            dp[t-1] = 0;
            per(i,t-1,0){
                for(int p: adj[i]){
                    dp[p] = max(dp[i] + 1, dp[p]);
                }
            } 
            int mx = -1;
            rep(i,0,t){
                if(!is[i]) mx = max(mx, dp[i]);
            }
            cout << mx << '\n';
        }
        for(int r: city) is[r] = false;
    }
    return 0;
}

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