제출 #334304

#제출 시각아이디문제언어결과실행 시간메모리
334304CannotACBitaro’s Party (JOI18_bitaro)C++11
7 / 100
2099 ms8164 KiB
#include <bits/stdc++.h>
#define FAST_IO ios_base:;sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FILE_NAME "BITARO"
#define ll long long

using namespace std;

const int MAXN = 100001;
int n, m, q, t, y;
int d[MAXN];
bool mark[MAXN];
vector<int> adj[MAXN];

void findPath(int uStart)
{
    memset(d, 0x3f, sizeof(d));
    d[uStart] = 0;

    priority_queue<pair<int, int> > pq;
    pq.push({0, uStart});

    while(!pq.empty()) {
        int u = pq.top().second;
        int du = -pq.top().first;
        pq.pop();

        if (du != d[u])
            continue;

        for (int v : adj[u]) {
            if (d[v] > d[u]-1) {
                d[v] = d[u]-1;
                pq.push({-d[v], v});
            }
        }
    }
}

int main()
{
//    ifstream cin(FILE_NAME".INP");
//    ofstream cout(FILE_NAME".OUT");

    cin >> n >> m >> q;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[v].push_back(u);
    }

    for (int loop = 1; loop <= q; ++loop) {
        cin >> t >> y;

        memset(mark, true, sizeof(mark));
        for (int i = 1; i <= y; ++i) {
            int c;
            cin >> c;
            mark[c] = false;
        }

        int res = 0;
        findPath(t);
        for (int i = 1; i <= n; ++i)
            if (mark[i])
                res = max(res, -d[i]);

        if (res == 0 && mark[t] == false)
            res = -1;
        cout << res << '\n';
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...