Submission #1269851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269851		k12_khoi	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1241 ms	415296 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second

const int N=1e5+5;
const int oo=1e9+1;

int n,m,request,x,y,k;
int a[N],dp[N];
bool IsBusy[N];
vector <int> g[N];

namespace sub1
{
    void dfs(int u)
    {
        if (!IsBusy[u]) dp[u]=0;
        else dp[u]=-oo;
        for (int v:g[u])
        {
            if (dp[v]==-1) dfs(v);

            dp[u]=max(dp[u],dp[v]+1);
        }
    }

    void solve()
    {
        while (request--)
        {
            cin >> x >> k;
            for (int j=1;j<=k;j++)
            {
                cin >> a[j];

                IsBusy[a[j]]=true;
            }

            for (int i=1;i<=n;i++)
            dp[i]=-1;

            dfs(x);

            if (dp[x]<0) dp[x]=-1;

            cout << dp[x] << '\n';


            for (int j=1;j<=k;j++)
            IsBusy[a[j]]=false;
        }
    }
}

namespace sub3
{
    int S;
    bool ok,used[N];
    vector <pii> mx_dist[N];

    vector <pii> MergeDist(vector <pii> A,vector <pii> B)
    {
        vector <pii> C;
        C.clear();

        for (int i=0;i<B.size();i++)
        B[i].X++;

        int l=0;
        int r=0;

        while (C.size()<S and l<A.size() and r<B.size())
        {
            if (A[l].X>B[r].X)
            {
                if (!used[A[l].Y])
                {
                    C.push_back(A[l]);
                    used[A[l].Y]=true;
                }

                l++;
            }
            else
            {
                if (!used[B[r].Y])
                {
                    C.push_back(B[r]);
                    used[B[r].Y]=true;
                }
                r++;
            }
        }

        while (C.size()<S and l<A.size())
        {
            if (!used[A[l].Y])
            {
                C.push_back(A[l]);
                used[A[l].Y]=true;
            }
            l++;
        }

        while (C.size()<S and r<B.size())
        {
            if (!used[B[r].Y])
            {
                C.push_back(B[r]);
                used[B[r].Y]=true;
            }
            r++;
        }

        for (pii j:C)
        used[j.Y]=false;

        return C;
    }

    void pre_dfs(int u)
    {
        mx_dist[u].push_back(make_pair(0,u));
        for (int v:g[u])
        {
            if (mx_dist[v].size()==0) pre_dfs(v);

            mx_dist[u]=MergeDist(mx_dist[u],mx_dist[v]);
        }
    }

    void dfs(int u)
    {
        if (!IsBusy[u]) dp[u]=0;
        else dp[u]=-oo;
        for (int v:g[u])
        {
            if (dp[v]==-1) dfs(v);

            dp[u]=max(dp[u],dp[v]+1);
        }
    }

    void solve()
    {
        S=trunc(sqrt(n));

        for (int i=1;i<=n;i++)
        if (mx_dist[i].size()==0)
            pre_dfs(i);

        while (request--)
        {
            cin >> x >> k;
            for (int j=1;j<=k;j++)
            {
                cin >> a[j];
                IsBusy[a[j]]=true;
            }

            if (k>=S)
            {
                for (int i=1;i<=n;i++)
                dp[i]=-1;

                dfs(x);

                if (dp[x]<0) dp[x]=-1;

                cout << dp[x] << '\n';
            }
            else
            {
                ok=false;

                for (pii j:mx_dist[x])
                if (!IsBusy[j.Y])
                {
                    ok=true;
                    cout << j.X << '\n';
                    break;
                }

                if (!ok) cout << -1 << '\n';
            }

            for (int j=1;j<=k;j++)
            IsBusy[a[j]]=false;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m >> request;
    for (int i=1;i<=m;i++)
    {
        cin >> x >> y;
        g[y].push_back(x);
    }

    sub3::solve();
}

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