Submission #1365377

#TimeUsernameProblemLanguageResultExecution timeMemory
1365377datBitaro’s Party (JOI18_bitaro)C++20
100 / 100
1020 ms343048 KiB
#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>

using namespace std;

const int Nmax = 1e5 + 5, Mmax = 2e5 + 5, Qmax = 1e5 + 5, S = 130;

int n, m, q;
bool busy[Nmax], used_node[Nmax];
vector<int> way[Nmax], rway[Nmax];
vector<pii> path[Nmax];

int getDist(int t) {
    vector<int> dp(t + 1, -1);
    for(int u = 1; u <= t; u++){
        if(!busy[u]) dp[u] = 0;

        for(int p: rway[u]){
            if(dp[p] != -1){
                dp[u] = max(dp[u], dp[p] + 1);
            }
        }
    }
    return dp[t];
}

void solve(){
    for(int i = 1; i <= n; i++){
        path[i].push_back({0, i});
    }

    for(int u = 1; u <= n; u++){
        for(int v: way[u]){
            auto &pv = path[v];

            for(auto [len, start]: path[u]){
                pv.push_back({len + 1, start});
            }
            sort(pv.begin(), pv.end(), greater<pii>());
            vector<pii> newlist;
            for(auto [len, start]: pv){
                if(!used_node[start]) {
                    newlist.push_back({len, start});
                    used_node[start] = true;
                }
                if(newlist.size() == S) break;
            }
            for(auto [len, start]: newlist){
                used_node[start] = false;
            }
            pv = newlist;
        }
    }
}


void enter(){
    cin >> n >> m >> q;
    int u, v, t, y, c;
    for(int i = 0; i < m; i++){
        cin >> u >> v;
        way[u].push_back(v);
        rway[v].push_back(u);
    }
    solve();
    for(int i = 0; i < q; i++){
        cin >> t >> y;
        memset(busy, false, sizeof(busy));
        vector<int> c(y);
        for(int j = 0; j < y; j++){
            cin >> c[j];
            busy[c[j]] = true;
        }
        if(y >= S) cout << getDist(t) << '\n';
        else {
            bool fail = true;
            for(auto [len, start]: path[t]){
                if(!busy[start]){
                    fail = false;
                    cout << len << '\n';
                    break;
                }
            }
            if(fail) cout << -1 << '\n';
        }
        for(int j = 0; j < y; j++){
            busy[c[j]] = false;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    enter();
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...