Submission #334657

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

bitaro

#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0);
#define FILE_NAME "BITARO"
#define ll long long
#define pb push_back
#define fi first
#define se second

using namespace std;

const int MAXN = 100001;
int n, m, q;
int d[MAXN], q_t[MAXN];
vector<int> adj[MAXN];
vector<bool> busy[MAXN];

void Dijkstra(int uStart)
{
    memset(d, -0x3F, sizeof(d));
    priority_queue<pair<int, int> > pq;

    d[uStart] = 0;
    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()
{
    FAST_IO;
//    freopen(FILE_NAME".INP", "r", stdin);
//    freopen(FILE_NAME".OUT", "w", stdout);

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

    for (int i = 1; i <= q; ++i) {
        int t, y;
        cin >> t >> y;
        q_t[i] = t;
        busy[i].resize(n+1, false);
        for (int j = 1; j <= y; ++j) {
            int c;
            cin >> c;
            busy[i][c] = true;
        }
    }

    for (int i = 1; i <= q; ++i) {
        Dijkstra(q_t[i]);
        int res = 0;
        for (int v = 1; v <= n; ++v)
            if (!busy[i][v])
                res = max(res, d[v]);
        if (res == 0 && busy[i][q_t[i]])
            res = -1;
        cout << res << '\n';
    }
    return 0;
}

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