Submission #1349499

#TimeUsernameProblemLanguageResultExecution timeMemory
1349499boropotoBitaro’s Party (JOI18_bitaro)C++20
14 / 100
1530 ms118640 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")

inline void speed()
{
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
}

const int maxn = 1e5 + 10, sq = 72;

static int n, m, q, x, y;
static int dp[maxn], mx[maxn];
static std::vector<int> v[maxn], v1[maxn];
static std::vector<std::pair<int,int>> s1[maxn];
static bool used[maxn], banned[maxn], can[maxn];

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;

    if(banned[i]) dp[i] = -1;
    else dp[i] = 0;

    for(const int& nb : v1[i])
    {
        if(!used[nb]) dfs(nb);
        if(dp[nb] != -1)
        {
            dp[i] = std::max(dp[i], dp[nb] + 1);
        }
    }
}

inline int large(const int& x, const int& y)
{
    for(int i = 1; i <= n; i++)
    {
        used[i] = 0;
    }

    std::vector<int> ban;
    int node;

    for(int i = 1; i <= y; i++)
    {
        std::cin >> node;
        banned[node] = 1;
        ban.push_back(node);
    }

    dfs(x);
    const int ans = dp[x];

    for(const int& node : ban)
    {
        banned[node] = 0;
    }

    return ans;
}

inline void dfs1(int i)
{
    std::vector<int> nodes = {i};
    mx[i] = 0;
    used[i] = 1;

    for(const int& nb : v1[i])
    {
        if(!used[nb]) dfs1(nb);

        for(const auto& j : s1[nb])
        {
            nodes.push_back(j.second);
            mx[j.second] = std::max(mx[j.second], j.first + 1);
        }
    }

    s1[i].clear();

    std::sort(nodes.begin(), nodes.end());

    s1[i].push_back({mx[nodes[0]], nodes[0]});
    mx[nodes[0]] = -1;

    for(int j = 1; j < (int)nodes.size(); j++)
    {
        if(nodes[j] != nodes[j - 1])
        {
            s1[i].push_back({mx[nodes[j]], nodes[j]});
            mx[nodes[j]] = -1;
        }
    }

    std::sort(s1[i].rbegin(), s1[i].rend());

    while((int)s1[i].size() > sq)
        s1[i].pop_back();
}

inline int small(const int& x, const int& y)
{
    std::vector<int> ban;
    int node;

    for(int i = 1; i <= y; i++)
    {
        std::cin >> node;
        banned[node] = 1;
        ban.push_back(node);
    }

    for(const std::pair<int,int>& j : s1[x])
    {
        if(!banned[j.second])
        {
            for(const int& node : ban)
            {
                banned[node] = 0;
            }
            return j.first;
        }
    }

    for(const int& node : ban)
    {
        banned[node] = 0;
    }

    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 << large(x, y) << '\n';
        }
        else
        {
            std::cout << small(x, y) << '\n';
        }
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...