Submission #1351117

#TimeUsernameProblemLanguageResultExecution timeMemory
1351117kantaponzBitaro’s Party (JOI18_bitaro)C++20
100 / 100
766 ms510700 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;

    for (auto v : adj[u]) {
        precompute_path(v);
        
        vector<pair<int,int>> next_path;
        int i = 0, j = 0;
        
        while ((i < path[u].size() || j < path[v].size()) && next_path.size() < b) {
            
            if (i < path[u].size() && (j == path[v].size() || path[u][i].first >= path[v][j].first + 1)) {
                if (!inList[path[u][i].second]) {
                    inList[path[u][i].second] = true;
                    next_path.push_back(path[u][i]);
                }
                i++;
            } 
            else {
                if (!inList[path[v][j].second]) {
                    inList[path[v][j].second] = true;
                    next_path.push_back({path[v][j].first + 1, path[v][j].second});
                }
                j++;
            }
        }
        
        for (auto p : next_path) {
            inList[p.second] = false;
        }
        
        path[u] = next_path;
    }
    path[u].emplace_back(0, u);

    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...