제출 #1132099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132099		AndrijaM	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	754 ms	288732 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

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

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

vector<int>g[maxn];
vector<int>rg[maxn];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ///freopen("dulciuri.in","r",stdin);
    ///freopen("dulciuri.out","w",stdout);
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        rg[b].push_back(a);
    }
    vector<vector<pair<int,int>>>l(n+1);
    vector<int>vis(n+1,-1);
    l[1]={{0,1}};
    for(int i=2;i<=n;i++)
    {
        vector<int>v;
        for(auto sosed:rg[i])
        {
            for(auto ax:l[sosed])
            {
                int dist=ax.first;
                int node=ax.second;
                if(vis[node]<0)
                {
                    v.push_back(node);
                }
                vis[node]=max(vis[node],dist+1);
            }
        }
        l[i].emplace_back(0,i);
        for(auto ax:v)
        {
            l[i].emplace_back(vis[ax],ax);
        }
        sort(l[i].begin(),l[i].end(),greater<>());
        if(l[i].size()>sz)
        {
            l[i].resize(sz);
        }
        for(auto ax:v)
        {
            vis[ax]=-1;
        }
    }
    for(int i=0;i<q;i++)
    {
        int t,y;
        cin>>t>>y;
        vector<int>b(y);
        for(int j=0;j<y;j++)
        {
            cin>>b[j];
        }
        set<int>bs(b.begin(),b.end());
        if(y>=sz)
        {
            vector<int>dp(t+1,-1);
            dp[t]=0;
            for(int node=t;node>=1;node--)
            {
                if(dp[node]==-1)continue;
                for(auto sosed:rg[node])
                {
                    dp[sosed]=max(dp[sosed],dp[node]+1);
                }
            }
            int mx=-1;
            for(int node=1;node<=t;node++)
            {
                if(!bs.count(node))
                {
                    mx=max(mx,dp[node]);
                }
            }
            cout<<mx<<endl;
        }
        else
        {
            int mx=-1;
            for(auto ax:l[t])
            {
                int dist=ax.first;
                int node=ax.second;
                if(!bs.count(node))
                {
                    mx=max(mx, dist);
                }
            }
            cout<<mx<<endl;
        }
    }
    return 0;
}

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