Submission #842567

#TimeUsernameProblemLanguageResultExecution timeMemory
842567magicianBitaro’s Party (JOI18_bitaro)C++14
100 / 100
1192 ms420280 KiB
#include<iostream>
#include<vector>
#include<cstring>

#define all(v) (v).begin(), (v).end()
#define sz(v) (int)(v).size()
#define fi first
#define se second

using namespace std;

const int NMAX = (int)1e5 + 10;
const int INF = (int)1e9 + 7;
const int B = 300;
int N, M, Q;
vector<int> adj[NMAX], radj[NMAX];
vector<pair<int, int>> good[NMAX];
bool used[NMAX];
bool ohno[NMAX];
int dp[NMAX];

int main(void) {
        ios_base::sync_with_stdio(0); cout.tie(0); cout.tie(0);
//        freopen("a.in", "r", stdin); freopen("a.out", "w", stdout);
        cin >> N >> M >> Q;
        for(int i = 1; i <= M; i++) {
                int u, v; cin >> u >> v;
                adj[u].push_back(v);
                radj[v].push_back(u);
        }
        memset(used, false, sizeof used);
        for(int i = 1; i <= N; i++) {
                for(int j = 0; j < sz(radj[i]); j++) {
                        vector<pair<int, int>> res;
                        int u = radj[i][j];
                        int a = 0, b = 0;
                        while(sz(res) < B && (a < sz(good[i]) || b < sz(good[u]))) {
                                if(b == sz(good[u]) || (a < sz(good[i]) && good[i][a].se >= good[u][b].se + 1)) {
                                        res.push_back(good[i][a]);
                                        used[good[i][a].fi] = true;
                                        a++;
                                }
                                else {
                                        res.push_back(make_pair(good[u][b].fi, good[u][b].se + 1));
                                        used[good[u][b].fi] = true;
                                        b++;
                                }
                                while(a < sz(good[i]) && used[good[i][a].fi]) a++;
                                while(b < sz(good[u]) && used[good[u][b].fi]) b++;
                        }
                        for(int k = 0; k < sz(res); k++) {
                                used[res[k].fi] = false;
                        }
                        swap(good[i], res);
                }
                good[i].push_back(make_pair(i, 0));
//                cout << "i : " << i << ", size: " << sz(good[i]) << '\n';
//                for(int j = 0; j < sz(good[i]); j++) {
//                        cout << good[i][j].fi << ' ' << good[i][j].se << '\n';
//                        if(j == sz(good[i]) - 1) cout << '\n';
//                }
        }
        memset(ohno, false, sizeof ohno);
        while(Q--) {
                int v, y; cin >> v >> y;
                vector<int> c(y);
                for(int &val : c) {
                        cin >> val;
                        ohno[val] = true;
                }
                if(y < B) {
                        int ans = -1;
                        for(int i = 0; i < sz(good[v]); i++) if(ohno[good[v][i].fi] == false) {
                                ans = good[v][i].se;
                                break;
                        }
                        cout << ans << '\n';
                }
                else {
                        for(int i = 1; i <= v; i++) dp[i] = (ohno[i] ? -1 : 0);
                        for(int i = 1; i <= v; i++) {
                                if(dp[i] < 0 ) continue;
                                for(int j = 0; j < sz(adj[i]); j++) {
                                        int u = adj[i][j];
                                        dp[u] = max(dp[u], dp[i] + 1);
                                }
                        }
                        cout << dp[v] << '\n';
                }
                for(int &val : c) {
                        ohno[val] = false;
                }
        }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...