Submission #1127834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127834		AndrijaM	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	15 ms	20804 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define endl '\n'

const int maxn=2e5+10;
const int mod=1e9+7;

vector<int>g[maxn];
vector<int>G[maxn];
int dp[maxn];
int c[maxn];
vector<int>v[maxn];
int pdp[maxn];
bool used[maxn];
vector<pair<int,int>>bst[maxn];

void dfs(int node,int par)
{
    for(auto ax:g[node])
    {
        if(ax==par)continue;
        dfs(ax,node);
        dp[node]=max(dp[node],dp[ax]+1);
    }
}


signed main()
{
    ios::sync_with_stdio(false);
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        a--;b--;
        g[b].push_back(a);
        G[a].push_back(b);
    }
    for(int i=0;i<n;i++)
    {
        bst[i].push_back({0,i});
    }
    for(int i=0;i<n;i++)
    {
        for(auto &[d,x]:bst[i])
        {
            d++;
        }
        for(auto ax:G[i])
        {
            vector<pair<int,int>>c;
            auto add = [&](pair<int,int> &a) {
                if (!used[a.second]) {
                    c.push_back(a);
                    used[a.second] = 1;
                }
            };
            int l=0;
            int r=0;
            while(c.size()<350)
            {
                if(l==bst[i].size() && r==bst[ax].size())
                {
                    break;
                }
                if (r==bst[ax].size() || (l<bst[i].size() && bst[i][l].first>bst[ax][r].first))
                    add(bst[i][l++]);
                else
                    add(bst[ax][r++]);
            }
            for(auto &[d,x]:c)
            {
                used[x]=0;
            }
            bst[ax]=c;
        }
        for(auto &[d,x]:bst[i])
        {
            d--;
        }
    }
    while(q--)
    {
        int st;
        int kol;
        cin>>st>>kol;
        st--;
        memset(dp,0,sizeof dp);
        for(int i=0;i<kol;i++)
        {
            cin>>c[i];
            used[c[i]]=1;
            c[i]--;
            dp[c[i]]=-1e9;
        }
        if(kol<350)
        {
            ///memset(dp,0,sizeof dp);
            dfs(st,-1);
            cout<<dp[st]<<endl;
            continue;
        }
        else
        {
            int ans=-1;
            for(auto ax:bst[st])
            {
                if(!used[ax.second])
                {
                    ans=ax.first;
                    break;
                }
            }
            cout<<ans<<endl;
        }
        for(int i=0;i<kol;i++)
        {
            used[c[i]]=0;
        }
    }
    return 0;
}

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