Submission #1349286

#TimeUsernameProblemLanguageResultExecution timeMemory
1349286boropotoBitaro’s Party (JOI18_bitaro)C++20
14 / 100
2009 ms364880 KiB
#include<bits/stdc++.h>
#define endl '\n'
#define X first
#define Y second
void speed()
{
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
}
const int maxn=1e5+10,sq=100;
int n,m,q,x,y;
int dp[maxn];
std::vector<int> v[maxn],v1[maxn];
std::vector<std::pair<int,int>> s[maxn],s1[maxn];
bool used[maxn],banned[maxn],can[maxn];
bool cmp1(std::pair<int,int> p1,std::pair<int,int> p2)
{
    if(p1.Y==p2.Y)
    {
        return p1.X<p2.X;
    }
    return p1.Y<p2.Y;
}
inline void read()
{
    std::cin>>n>>m>>q;
    int x1,y1;
    for(int i=1; i<=m; i++)
    {
        std::cin>>x1>>y1;
        v[x1].push_back(y1);
        v1[y1].push_back(x1);
    }
}
inline void dfs(int i)
{
    used[i]=1;
    for(auto nb:v[i])
    {
        if(used[nb]==0)
        {
            dfs(nb);
        }
        if(can[nb]==1)
        {
            dp[i]=std::max(dp[i],dp[nb]+1);
            can[i]=1;
        }
    }
}
inline int small(int x,int y)
{
    for(int i=1; i<=n; i++)
    {
        used[i]=banned[i]=dp[i]=can[i]=0;
    }
    can[x]=1;
    for(int i=x; i>=1; i--)
    {
        if(used[i]==0)
        {
            dfs(i);
        }
    }
    int node;
    for(int i=1; i<=y; i++)
    {
        std::cin>>node;
        banned[node]=1;
    }
    int ans=-1;
    for(int i=1; i<=x; i++)
    {
        if(banned[i]==1||can[i]==0)
        {
            continue;
        }
        ans=std::max(ans,dp[i]);
    }
    if(ans==0&&banned[x]==1)
    {
        return -1;
    }
    return ans;
}
inline void dfs1(int i)
{
    used[i]=1;
    s[i].push_back({0,i});
    for(auto nb:v1[i])
    {
        if(used[nb]==0)
        {
            dfs1(nb);
        }
        for(auto j:s1[nb])
        {
            s[i].push_back({j.X+1,j.Y});
        }
    }
    sort(s[i].begin(),s[i].end(),cmp1);
    for(int j=0;j<s[i].size();)
    {
        if(j<s[i].size()-1)
        {
            while(j<s[i].size()&&s[i][j].Y==s[i][j+1].Y)
            {
                j++;
            }
        }
        s1[i].push_back(s[i][j]);
        j++;
    }
    sort(s1[i].rbegin(),s1[i].rend());
    while(s1[i].size()>sq+1)
    {
        s1[i].pop_back();
    }
}
inline int large(int x,int y)
{
    for(int i=1; i<=n; i++)
    {
        banned[i]=0;
    }
    int node;
    for(int i=1;i<=y;i++)
    {
        std::cin>>node;
        banned[node]=1;
    }
    for(auto j:s1[x])
    {
        if(banned[j.Y]==0)
        {
            return j.X;
        }
    }
    return -1;
}
int main()
{
    speed();
    read();
    for(int i=1;i<=n;i++)
    {
        if(used[i]==0)
        {
            dfs1(i);
        }
    }
    int x,y;
    for(int i=1;i<=q;i++)
    {
        std::cin>>x>>y;
        if(y>sq)
        {
            std::cout<<small(x,y)<<endl;
        }
        else
        {
            std::cout<<large(x,y)<<endl;
        }
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...