Submission #601196

#	Time	Username	Problem	Language	Result	Execution time	Memory
601196		boris_mihov	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1141 ms	264324 KiB

bitaro

#include <iostream>
#include <cstring>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXSQ = 320;
const int INF = 1e9;

std::vector <int> g[MAXN];
std::pair < int,int > dp[MAXN][MAXSQ];
std::pair < int,int > buff[MAXSQ];
bool inDP[MAXN];
int bucketSize;
bool bl[MAXN];
bool bl2[MAXN];
int dp2[MAXN];
int n, m, q;

void calcDP(int node)
{
    bl2[node] = true;
    std::fill(dp[node]+1, dp[node]+bucketSize, std::make_pair(0, -INF)); 
    dp[node][0] = {node, 0};

    for (int i : g[node])
    {
        if (!bl2[i]) calcDP(i);
        int lp = 0, rp = 0;

        for (int j = 0 ; j < bucketSize ; ++j)
        {
            dp[i][j].second++;
        }

        for (int j = 0 ; j < bucketSize ; ++j)
        {
            while (dp[node][lp].first != 0 && bl[dp[node][lp].first]) lp++;
            while (dp[i][rp].first != 0 && bl[dp[i][rp].first]) rp++;
            if (dp[node][lp].second > dp[i][rp].second)
            {
                bl[dp[node][lp].first] = true;
                buff[j] = dp[node][lp];
                lp++;
            } else
            {
                bl[dp[i][rp].first] = true;
                buff[j] = dp[i][rp];
                rp++;
            }
        }

        for (int j = 0 ; j < bucketSize ; ++j)
        {
            bl[dp[node][j].first] = false;
            bl[dp[i][j].first] = false;
            dp[node][j] = buff[j];
            dp[i][j].second--;
        }       
    }
}

int f(int node)
{
    if (bl2[node]) return dp2[node];
    bl2[node] = true;
    dp2[node] = -INF;
    if (!bl[node]) dp2[node] = 0;

    for (int i : g[node])
    {
        dp2[node] = std::max(dp2[node], f(i) + 1);
    }

    return dp2[node];
}

void solve()
{
    bucketSize = 317;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (bl2[i]) continue;
        calcDP(i);
    }

    std::vector <int> curr;
    for (int i = 1 ; i <= q ; ++i)
    {
        int node, count;
        std::cin >> node >> count;
        curr.clear();
        curr.resize(count + 1);
        for (int j = 1 ; j <= count ; ++j)
        {
            std::cin >> curr[j];
            bl[curr[j]] = true;
        }

        if (count <= bucketSize-1)
        {
            for (int i = 0 ; i <= bucketSize ; ++i)
            {
                if (bl[dp[node][i].first]) continue;
                if (dp[node][i].second < 0) std::cout << -1 << '\n';
                else std::cout << dp[node][i].second << '\n';
                break;
            }
        } else
        {
            memset(bl2, false, sizeof(bl2));
            int res = f(node);
            if (res < 0) std::cout << -1 << '\n';
            else std::cout << res << '\n';
        }

        for (int j = 1 ; j <= count ; ++j)
        {
            bl[curr[j]] = false;
        }
    }
}

void read()
{
    int x, y;
    std::cin >> n >> m >> q;
    for (int i = 1 ; i <= m ; ++i)
    {
        std::cin >> x >> y;
        g[y].push_back(x);
    }
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIO();
    read();
    solve();

    return 0;
}


/*
5 6 1
1 2
2 4
3 4
1 3
3 5
4 5
4 1 1

5 2 2 3
2 3 1 4 5

*/

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