Submission #798990

#	Time	Username	Problem	Language	Result	Execution time	Memory
798990		vjudge1	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2069 ms	16560 KiB

bitaro

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 10;
const int INF = 1e9;

vector<int> g[N];
int n, m, q;
vector<int> order;
bool us[N];

void topsort(int v) {
    us[v] = 1;
    for(int to : g[v]) {
        if(us[to]) continue;
        topsort(to);
    }
    order.push_back(v);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }
    for(int i = 1; i <= n; i++) {
        if(us[i]) continue;
        topsort(i);
    }
    while(q--) {
        int t, y;
        cin >> t >> y;
        set<int> st;
        for(int i = 0; i < y; i++) {
            int v;
            cin >> v;
            st.insert(v);
        }
        vector<int> dp(n + 1, -2 * INF);
        dp[t] = 0;
        for(int cur : order) {
            for(int to : g[cur]) dp[cur] = max(dp[cur], dp[to] + 1);
        }
        int ans = -INF;
        for(int i = 1; i <= n; i++) {
            if(st.count(i)) continue;
            ans = max(ans, dp[i]);
        }
        if(ans == -INF) ans = -1;
        cout << ans << '\n';
    }
}

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