Submission #483294

#	Time	Username	Problem	Language	Result	Execution time	Memory
483294		alextodoran	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1442 ms	120004 KiB

bitaro

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;

int N, M, Q;

vector <int> out[N_MAX + 2];
vector <int> in[N_MAX + 2];

int K;

vector <pair <int, int>> dp[N_MAX + 2];

bool aux[N_MAX + 2];

int maxLen[N_MAX + 2];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M >> Q;
    for(int i = 1; i <= M; i++)
    {
        int u, v;
        cin >> u >> v;

        out[u].push_back(v);
        in[v].push_back(u);
    }

    K = 100;

    for(int u = 1; u <= N; u++)
    {
        vector <pair <int, int>> vec;
        for(int v : in[u])
        {
            for(pair <int, int> p : dp[v])
                vec.push_back(p);
        }
        sort(vec.begin(), vec.end(), greater <pair <int, int>> ());

        for(pair <int, int> p : vec)
            if(aux[p.second] == false)
            {
                aux[p.second] = true;
                dp[u].push_back(make_pair(p.first + 1, p.second));
                if((int) dp[u].size() == K)
                    break;
            }
        if((int) dp[u].size() < K)
            dp[u].push_back(make_pair(0, u));

        for(pair <int, int> p : dp[u])
            aux[p.second] = false;
    }

    for(int i = 1; i <= Q; i++)
    {
        int u;
        cin >> u;

        int cnt;
        cin >> cnt;
        vector <int> exclude (cnt);
        for(int j = 0; j < cnt; j++)
            cin >> exclude[j];

        for(int v : exclude)
            aux[v] = true;

        if(cnt < K)
        {
            int pos = 0;
            while(pos < (int) dp[u].size() && aux[dp[u][pos].second] == true)
                pos++;
            if(pos == (int) dp[u].size())
                cout << "-1\n";
            else
                cout << dp[u][pos].first << "\n";
        }
        else
        {
            for(int v = 1; v <= N; v++)
            {
                maxLen[v] = (aux[v] == false ? 0 : INT_MIN);
                for(int w : in[v])
                    maxLen[v] = max(maxLen[v], maxLen[w] + 1);
            }
            if(maxLen[u] < 0)
                cout << "-1\n";
            else
                cout << maxLen[u] << "\n";
        }

        for(int v : exclude)
            aux[v] = false;
    }

    return 0;
}

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