Submission #1351096

#TimeUsernameProblemLanguageResultExecution timeMemory
1351096kantaponzBitaro’s Party (JOI18_bitaro)C++20
14 / 100
496 ms17144 KiB
#include <bits/stdc++.h>
using namespace std;

const int nx = 1e5 + 5;

const int b = 2;

int n, m, q;
vector<int> adj[nx];
vector<pair<int,int>> path[nx];
int dp[nx];
bool ban[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;
    map<int,int> mp;
    for (auto v : adj[u]) {
        precompute_path(v);
        for (auto [dist, idx] : path[v]) {
            auto it = mp.find(idx);
            if (it == mp.end()) mp[idx] = dist;
            else it->second = max(it->second, dist);
        }
    }
    path[u].emplace_back(0, u);
    int ct = 0;
    for (auto [k, v] : mp) {
        path[u].emplace_back(v + 1, k);
        ct++;
        if (ct >= b) break;
    }
    sort(path[u].begin(), path[u].end(), greater<pair<int,int>>());
    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...