제출 #1320524

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1320524		AMel0n	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	4 ms	928 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9 + 7;
const int SQRT = 300;

// bitarooo

int N, M, Q;
signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N >> M >> Q;
    vector<vector<int>> adj(N); // reversed
    for(int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        adj[b].push_back(a); // topo sorted alr
    }
    vector<vector<pair<int,int>>> dp(N);
    for(int v = 0; v < N; v++) {
        dp[v].emplace_back(0, v);
        unordered_map<int, int> victor;
        for(int &u: adj[v]) {
            for(auto &[dist, start]: dp[u]) { // MsqrtN
                victor[start] = max(victor[start], dist + 1);
            }
        }
        for(auto &[start, dist]: victor) {
            dp[v].emplace_back(dist, start);
        }
        sort(dp[v].begin(), dp[v].end());
        reverse(dp[v].begin(), dp[v].end());
        while(dp[v].size() >= SQRT) dp[v].pop_back(); 
    }
    for(int i = 0; i < Q; i++) {
        int t, y;
        cin >> t >> y;
        t--;
        unordered_set<int> cant;
        for(int j = 0; j < y; j++) {
            int x;
            cin >> x;
            x--;
            cant.insert(x);
        }
        if (y < SQRT) {
            bool yes = false;
            for(int k = 0; k < dp[t].size(); k++) {
                if (cant.find(dp[t][k].second) == cant.end()) {
                    yes = true;
                    cout << dp[t][k].first << endl;
                    break;
                }
            }
            if (!yes) cout << -1 << endl;
        } else {
            vector<vector<pair<int,int>>> dp2(N);
            for(int v = 0; v <= t; v++) {
                if (cant.find(v) != cant.end() && v != t) continue;
                if (cant.find(v) == cant.end()) dp2[v].emplace_back(0, v);
                unordered_map<int, int> victor;
                for(int &u: adj[v]) {
                    for(auto &[dist, start]: dp2[u]) {
                        victor[start] = max(victor[start], dist + 1);
                    }
                }
                for(auto &[start, dist]: victor) {
                    dp2[v].emplace_back(dist, start);
                }
                sort(dp2[v].begin(), dp2[v].end());
                reverse(dp2[v].begin(), dp2[v].end());
            }
            if (dp2[t].size()) cout << dp2[t][0].first << endl;
            else cout << -1;
        }
    }
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86