Submission #842559

#	Time	Username	Problem	Language	Result	Execution time	Memory
842559		magician	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	801 ms	420044 KiB

bitaro

#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 ohno[NMAX];
int dp[NMAX];

int main(void) {
        ios_base::sync_with_stdio(0); cout.tie(0); cout.tie(0);
        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);
        }
        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)) {
                                        if(res.empty() || good[i][a].fi != res.back().fi)
                                                res.push_back(good[i][a]);
                                        a++;
                                }
                                else {
                                        if(res.empty() || good[u][b].fi != res.back().fi)
                                                res.push_back(make_pair(good[u][b].fi, good[u][b].se + 1));
                                        b++;
                                }
                        }
                        swap(good[i], res);
                }
                good[i].push_back(make_pair(i, 0));
        }
        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;
                }
        }
}

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