제출 #1349413

#제출 시각아이디문제언어결과실행 시간메모리
1349413boropotoBitaro’s Party (JOI18_bitaro)C++20
14 / 100
2095 ms74004 KiB
#include<iostream>
#include<vector>
#include<algorithm>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx")
#pragma GCC target("avx2")
#pragma GCC target("fma")
#pragma GCC target("sse")
#pragma GCC target("sse2")
#pragma GCC target("sse3")
#pragma GCC target("ssse3")
#pragma GCC target("sse4")
#pragma GCC target("popcnt")
inline void speed()
{
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
}
const int maxn = 1e5 + 10, sq =50;
int n, m, q, x, y;
int dp[maxn];
std::vector<int> v[maxn], v1[maxn];
std::vector<std::pair<int,int>> s, s1[maxn];
bool used[maxn], banned[maxn], can[maxn];
bool cmp1(const std::pair<int,int>& p1, const std::pair<int,int>& p2)
{
    if(p1.second == p2.second) return p1.first < p2.first;
    return p1.second < p2.second;
}
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(const int i)
{
    used[i] = 1;
    for(const int& nb : v[i])
    {
        if(!used[nb]) dfs(nb);
        if(can[nb])
        {
            dp[i] = std::max(dp[i], dp[nb] + 1);
            can[i] = 1;
        }
    }
}
inline int small(const int x, const 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(const int i)
{
    s.clear();
    used[i] = 1;
    s.push_back({0, i});
    for(const int& nb : v1[i])
    {
        if(!used[nb]) dfs1(nb);
        for(const std::pair<int,int>& j : s1[nb])
        {
            s.push_back({j.first + 1, j.second});
        }
    }
    std::sort(s.begin(), s.end(), cmp1);
    for(int j=0;j<s.size();)
    {
        if(j<s.size()-1)
        {
            while(j<s.size()&&s[j].second==s[j+1].second)
            {
                j++;
            }
        }
        s1[i].push_back(s[j]);
        j++;
    }
    std::sort(s1[i].rbegin(), s1[i].rend());
    while((int)s1[i].size() > sq)
    {
        s1[i].pop_back();
    }
}
inline int large(const int x, const 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(const std::pair<int,int>& j : s1[x])
    {
        if(!banned[j.second]) return j.first;
    }
    return -1;
}
int main()
{
    speed();
    read();
    for(int i = 1; i <= n; i++)
    {
        if(!used[i]) dfs1(i);
    }
    for(int i = 1; i <= q; i++)
    {
        std::cin >> x >> y;
        if(y > sq)
        {
            std::cout << small(x, y) << '\n';
        }
        else
        {
            std::cout << large(x, y) << '\n';
        }
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...