Submission #536364

#	Time	Username	Problem	Language	Result	Execution time	Memory
536364		AA_Surely	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1092 ms	272104 KiB

bitaro

#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(int i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(int i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;
typedef long long 		LL;

typedef pair<int, int> 	PII;
typedef pair<LL, LL> 	PLL;

typedef vector<int> 	VI;
typedef vector<LL> 		VLL;
typedef vector<PII> 	VPII;
typedef vector<PLL> 	VPLL;

const int MAXN = 1e5 + 7;
const int ALPHA = 27;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;
const int SQ = 320;

int n, m, q, cnt;
int skip[MAXN], mem[MAXN], marked[MAXN];
int tmp[SQ][2], dp[MAXN][SQ][2];
bool colored[MAXN];
VI adj[MAXN], order, radj[MAXN];

void init() {
    cin >> n >> m >> q;

    int u, v;
    F0R(i, m) {
        cin >> u >> v;
        adj[--u].pb(--v);
        radj[v].pb(u);
    }

    return;
}

void dfs(int now) {
    colored[now] = 1;

    for(int on : adj[now]) if (!colored[on]) dfs(on);
    order.pb(now);

    return;
}

inline int merge(int (&a)[SQ][2], int (&b)[SQ][2], int (&c)[SQ][2]) {
    cnt++;
    int aptr = 0, bptr = 0, cptr = 0;
    F0R(i, SQ) c[i][0] = c[i][1] = 0;

    while(aptr < SQ && bptr < SQ && a[aptr][0] && b[bptr][0] && cptr < SQ) {
        if (a[aptr][0] > b[bptr][0]) {
            if (marked[ a[aptr][1] ] == cnt) {
                aptr++;
                continue;
            }
            c[cptr][0] = a[aptr][0];
            c[cptr][1] = a[aptr][1];

            marked[ a[aptr][1] ] = cnt;
            aptr++; cptr++;
        }

        else {
            if (marked[ b[bptr][1] ] == cnt) {
                bptr++;
                continue;
            }

            c[cptr][0] = b[bptr][0] + 1;
            c[cptr][1] = b[bptr][1];

            marked[ b[bptr][1] ] = cnt;
            bptr++; cptr++;
        }
    }

    while(aptr < SQ && a[aptr][0] && cptr < SQ) {

        if (marked[ a[aptr][1] ] == cnt) {
            aptr++;
            continue;
        }

        c[cptr][0] = a[aptr][0];
        c[cptr][1] = a[aptr][1];

        marked[ a[aptr][1] ] = cnt;
        aptr++; cptr++;
    }

    while(bptr < SQ && b[bptr][0] && cptr < SQ) {
        if (marked[ b[bptr][1] ] == cnt) {
            bptr++;
            continue;
        }

        c[cptr][0] = b[bptr][0] + 1;
        c[cptr][1] = b[bptr][1];

        marked[ b[bptr][1] ] = cnt;
        bptr++; cptr++;
    }

    return cptr;
}

void precalc() {
    F0R(i, n) if (!colored[i]) dfs(i);
    reverse(ALL(order));

    /*for(int on : order) cout << on << ' ';
    cout << endl;*/


    F0R(i, n) {
        int now = order[i];

        dp[now][0][0] = 1;
        dp[now][0][1] = now;

        for(int on : radj[now]) {
            merge(dp[now], dp[on], tmp);

            F0R(i, SQ) {
                dp[now][i][0] = tmp[i][0];
                dp[now][i][1] = tmp[i][1];
            }
        }
    }

    return;
}

void calc(int p) {
    fill(mem, mem + MAXN, -INF);

    F0R(i, n) {
        int now = order[i];
        if (skip[now] != p) mem[now] = 1;

        for(int on : radj[now]) 
            mem[now] = max(mem[now], mem[on] + 1);
    }

    return;
}

#define endl '\n'

int main() {
    IOS;

    init();
    precalc();

    /*F0R(i, n) {
        cout << i + 1 << " : ";
        for(int on : radj[i]) cout << on + 1 << ' ';
        cout << endl;
    }*/
    
    //F0R(i, 5) cout << dp[3][i][0] << ' ' << dp[3][i][1] << endl;

    FOR(p, 1, q + 1) {
        int t, k, x;
        cin >> t >> k;
        t--;

        F0R(i, k) {
            cin >> x; x--;
            skip[x] = p;
        }
        /*F0R(i, n) cout << skip[i] << ' ';
        cout << endl;*/

       if (k < SQ) {
            bool done = 0;
            F0R(i, SQ) if (skip[ dp[t][i][1] ] != p) {
                cout << dp[t][i][0] - 1 << endl;
                done = 1;
                break;
            }
            if (!done) cout << -1 << endl;
        }
        
        else {
            calc(p);
            cout << (mem[t] > 0 ? mem[t] - 1 : -1) << endl;
        }
    }
}

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