제출 #1351111

#제출 시각아이디문제언어결과실행 시간메모리
1351111kantaponzBitaro’s Party (JOI18_bitaro)C++20
7 / 100
2094 ms6224 KiB
#include <bits/stdc++.h>
using namespace std;

const int nx = 1e5 + 5;

const int b = 317;

int n, m, q;
vector<int> adj[nx];
vector<pair<int,int>> path[nx];
int dp[nx];
bool ban[nx];
bool inList[nx];

int solve(int u) {
    if (dp[u] != -1) return dp[u];
    int ans = 0;
    for (auto v : adj[u]) {
        ans = max(ans, solve(v));
    }
    if (ban[u]) {
        if (ans != 0) return dp[u] = ans + 1;
        return dp[u] = ans;
    }
    return dp[u] = ans + 1;
}

void precompute_path(int u) {
    if (!path[u].empty()) return;
    vector<pair<int,int>> tmp;
    for (auto v : adj[u]) {
        precompute_path(v);
        for (auto [dist, idx] : path[v]) {
            tmp.emplace_back(dist + 1, idx);
        }
    }
    path[u].emplace_back(0, u);
    sort(tmp.begin(), tmp.end(), greater<pair<int,int>>());
    int ct = 0;
    for (auto [d, x] : tmp) {
        if (inList[x]) continue;
        path[u].emplace_back(d, x);
        ct++;
        inList[x] = 1;
        if (ct >= b) break;
    }
    sort(path[u].begin(), path[u].end(), greater<pair<int,int>>());
    for (auto [d, x] : path[u]) inList[x] = 0;

    return;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> q;
    while (m--) {
        int u, v;
        cin >> u >> v;
        adj[v].emplace_back(u);
    }
    for (int u = 1; u <= n; u++) {
        precompute_path(u);
        /*printf("%d : ", u);
        for (auto [k, v] : path[u]) {
            printf("(%d, %d) ", k, v);
        }
        printf("\n");*/
    }

    while (q--) {
        int t, y;
        cin >> t >> y;
        if (y < b) {
            vector<int> ban(y);
            for (int i = 0; i < y; i++) cin >> ban[i];
            int ans = -1;
            for (auto [dist, start] : path[t]) {
                auto it = lower_bound(ban.begin(), ban.end(), start);
                //printf("%d ", *it);
                if (it != ban.end() && *it == start) continue;
                ans = dist;
                break;
            }
            printf("%d\n", ans);
        } else {
            memset(dp, -1, sizeof dp);
            memset(ban, 0, sizeof ban);
            for (int i = 0; i < y; i++) {
                int x; cin >> x;
                ban[x] = 1;
            }
            printf("%d\n", solve(t) - 1);
        }
    }


}

/*
5 6 3
1 2
2 4
3 4
1 3
3 5
4 5
4 1 1
5 2 2 3
2 3 1 4 5


1
3
0

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