Submission #1132547

#TimeUsernameProblemLanguageResultExecution timeMemory
1132547lopkusBitaro’s Party (JOI18_bitaro)C++20
0 / 100
2100 ms126304 KiB
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 5;

vector<int> adj[N];

int n, m, q;

vector<int> dist(N, - 1);

void bfs(int x) {
    deque<int> q;
    dist[x] = 0;
    q.push_back(x);
    while(q.size()) {
        int cvor = q.front();
        q.pop_front();
        for(auto it : adj[cvor]) {
            dist[it] = max(dist[it], dist[cvor] + 1);
            q.push_back(it);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        if(u > v) {
            swap(u, v);
        }
        adj[v].push_back(u);
    }
    while(q--) {
        int t;
        cin >> t;
        int s;
        cin >> s;
        bfs(t);
        vector<int> Q(n + 1, 0);
        while(s--) {
            int x;
            cin >> x;
            Q[x] = 1;
        }
        int ans = -1;
        for(int i = 1; i <= n; i++) {
            if(dist[i] != - 1) {
                if(Q[i]) {
                    continue;
                }
                ans = max(ans, dist[i]);
            }
        }
        cout << ans << "\n";
        for(int i = 1; i <= n; i++) {
            dist[i] = - 1;
        }
    }
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...