Submission #702106

#	Time	Username	Problem	Language	Result	Execution time	Memory
702106		AmirElarbi	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1693 ms	219260 KiB

bitaro

#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
//#define mp make_pair
#define fi first
#define se second
#define INF 1e9
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 2e5+5
using namespace std;
const int MOD = 998244353;
const int nax = 1e5+5;
const int nax2 =  20;
typedef complex<int> Point;
using cd = complex<double>;
const int batch = 150;
vi prv[nax], dp;
vii fr[nax];
int vis[nax], val[nax], cur[nax], cnt = 0;
int dfs(int u, int q){
    int mx = 0;
    if(cur[u] == q) mx = -1;
    for(auto x : prv[u]){
        if(dp[x] == -1) continue;
        if(dp[x] != -2) {
            mx = max(mx,dp[x]+1);
            continue;
        }
        int a = dfs(x,q);
        if(a == -1) continue;
        mx = max(mx, a+1);
    }
    return dp[u] = mx;
}
bool cmp(int x, int y){
    return val[x] > val[y];
}
int main()
{
    optimise;
    int n,m,q;
    cin >> n >> m >> q;
    for(int i = 0;i < m; i++){
        int x,y;
        cin >> x >> y;
        x--,y--;
        prv[y].pb(x);
    }
    for(int i= 0; i < n; i++){
        ve<int> all;
        for(auto x : prv[i]){
            for(auto y : fr[x]){
                if(vis[y.se] != i){
                    vis[y.se] = i;
                    all.pb(y.se);
                    val[y.se] = y.fi+1;
                } else val[y.se] = max(val[y.se], y.fi+1);
            }
            if(vis[x] != i){
                vis[x] = i;
                all.pb(x);
                val[x] = 1;
            }
        }
        all.pb(i);
        sort(all.begin(), all.end(), cmp);
        for(int j = 0; j < min(batch, (int) all.size()); j++){
            fr[i].pb({val[all[j]], all[j]});
        }
    }
    memset(cur, -1,sizeof cur);
    while(q--){
        int l; cin >> l; l--;
        int r; cin >> r;
        for(int i = 0; i < r; i++){
            int x;
            cin >> x;
            cur[x-1] = q;
        } 
        if(r < batch){
            int res = -1;
            for(auto x : fr[l]){
                if(cur[x.se] == q) continue;
                res = x.fi;
                break;  
            }
            cout << res << endl;
        } else {
            dp.clear();
            dp.assign(n,-2);
            cout << dfs(l, q) << endl;
        }
    }
}

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