Submission #483882

#	Time	Username	Problem	Language	Result	Execution time	Memory
483882		blue	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2080 ms	12220 KiB

bitaro

#include <iostream>
#include <vector>
using namespace std;

const int rt = -1;
const int INF = 1'000'000'000;

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

    int N, M, Q;
    cin >> N >> M >> Q;

    vector<int> edge[1+N];
    vector<int> rev_edge[1+N];

    for(int j = 1; j <= M; j++)
    {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        rev_edge[v].push_back(u);
    }


    for(int q = 1; q <= Q; q++)
    {
        int T, Y;
        cin >> T >> Y;

        vector<int> C(Y);
        for(int i = 0; i < Y; i++) cin >> C[i];

        if(Y > rt)
        {
            vector<bool> excluded(1+N, 0);
            for(int c:C) excluded[c] = 1;
            vector<int> maxdist(1+N, -INF);

            for(int i = 1; i <= T; i++)
            {
                if(!excluded[i]) maxdist[i] = 0;
                for(int j: rev_edge[i]) maxdist[i] = max(maxdist[i], 1 + maxdist[j]);
            }

            if(maxdist[T] < 0) maxdist[T] = -1;
            cout << maxdist[T] << '\n';
        }
        else
        {
            cout << "!\n";
        }
    }
}

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