Submission #334304

#	Time	Username	Problem	Language	Result	Execution time	Memory
334304		CannotAC	Bitaro’s Party (JOI18_bitaro)	C++11	7 / 100	2099 ms	8164 KiB

bitaro

#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;
}

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