Submission #1359203

#TimeUsernameProblemLanguageResultExecution timeMemory
1359203njoopBitaro’s Party (JOI18_bitaro)C++20
14 / 100
1974 ms483132 KiB
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g;
vector<set<pair<int, int>>> path;
vector<int> dp;
int n, m, q;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> q;
    g.assign(n+2, vector<int>());
    path.assign(n+2, set<pair<int, int>>());
    while(m--) {
        int u, v;
        cin >> u >> v;
        if(u > v) swap(u, v);
        g[u].push_back(v);
    }
    for(int i=1; i<=n; i++) {
        path[i].insert({0, i});
        while(path[i].size() > 100) {
            path[i].erase(path[i].begin());
        }
        for(auto j: g[i]) {
            for(auto k: path[i]) {
                path[j].insert({k.first+1, k.second});
            }
        }
    }
    while(q--) {
        int t, y;
        set<int> blk;
        cin >> t >> y;
        for(int i=1; i<=y; i++) {
            int in;
            cin >> in;
            blk.insert(in);
        }
        if(y >= 100) {
            dp.assign(n+2, -1);
            for(int i=1; i<=t; i++) {
                if(blk.find(i) == blk.end()) dp[i] = max(dp[i], 0);
                if(dp[i] == -1) continue;
                for(auto j: g[i]) {
                    dp[j] = max(dp[j], dp[i]+1);
                }
            }
            cout << dp[t] << "\n";
        } else {
            set<pair<int, int>> s = path[t];
            while(!s.empty()) {
                auto x = *s.rbegin();
                if(blk.find(x.second) == blk.end()) {
                    cout << x.first << "\n";
                    break;
                }
                if(s.size() > 1) s.erase(prev(s.end()));
                else s.erase(s.begin());
            }
            if(s.empty()) {
                cout << "-1\n";
            }
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...