Submission #440653

#	Time	Username	Problem	Language	Result	Execution time	Memory
440653		benedict0724	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	2000 ms	252252 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;
const int BUCKET_SIZE = 302;
const int MAX_N = 100002;

vector<int> adj[MAX_N], inv[MAX_N];
pair<int, int> Town[MAX_N][BUCKET_SIZE];
pair<int, int> tmp[BUCKET_SIZE];
bool Used[MAX_N];
int dp[MAX_N];

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M, Q; cin >> N >> M >> Q;
    for(int i=1;i<=M;i++)
    {
        int S, E; cin >> S >> E;
        adj[S].push_back(E);
        inv[E].push_back(S);
    }
    for(int i=1;i<=N;i++) Town[i][0] = {i, 0};
    for(int i=1;i<=N;i++)
    {
        for(int j : adj[i])
        {
            int x=0, y=0;
            stack<int> st;
            for(int b=0;b<BUCKET_SIZE;b++) tmp[b] = {0, 0};
            for(int b=0;b<BUCKET_SIZE;)
            {
                int A = Town[i][x].first, B = Town[i][x].second + 1;
                int C = Town[j][y].first, D = Town[j][y].second;
                if(A == 0 && C == 0) break;
                if(A == 0 || D > B)
                {
                    if(!Used[C])
                    {
                        st.push(C);
                        Used[C] = true;
                        tmp[b++] = {C, D};
                    }
                    y++;
                }
                else
                {
                    if(!Used[A])
                    {
                        st.push(A);
                        Used[A] = true;
                        tmp[b++] = {A, B};
                    }
                    x++;
                }
            }
            while(!st.empty())
            {
                Used[st.top()] = false;
                st.pop();
            }
            for(int b=0;b<BUCKET_SIZE;b++)
            {
                Town[j][b] = tmp[b];
            }
        }
    }

    for(int i=1;i<=Q;i++)
    {
        int T, Y;
        cin >> T >> Y;
        if(Y < BUCKET_SIZE)
        {
            stack<int> st;
            for(int j=0;j<Y;j++)
            {
                int k; cin >> k;
                Used[k] = true;
                st.push(k);
            }
            int ans = -1;
            for(int b=0;b<BUCKET_SIZE;b++)
            {
                if(Town[T][b].first == 0) break;
                if(!Used[Town[T][b].first])
                {
                    ans = Town[T][b].second;
                    break;
                }
            }
            while(!st.empty())
            {
                Used[st.top()] = false;
                st.pop();
            }
            cout << ans << "\n";
        }
        else
        {
            stack<int> st;
            for(int j=0;j<Y;j++)
            {
                int k; cin >> k;
                Used[k] = true;
                st.push(k);
            }
            int ans = -1;
            for(int j=1;j<=N;j++) dp[j] = -1;
            dp[T] = 0;

            for(int j=T;j>=2;j--) if(dp[j] != -1) for(int k : inv[j]) dp[k] = max(dp[k], dp[j] + 1);
            for(int j=1;j<=N;j++) if(!Used[j]) ans = max(ans, dp[j]);
            while(!st.empty())
            {
                Used[st.top()] = false;
                st.pop();
            }

            cout << ans << "\n";
        }
    }
}

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