제출 #1175349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175349		1bin	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	364 ms	245704 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int sqt = 300;
const int NMAX = 1e5 + 5;
int n, m, Q, a, b, D[NMAX][sqt + 5], V[NMAX][sqt + 5], T, Y, no[NMAX], dp[NMAX], vis[NMAX];
vector<int> adj[NMAX];

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> Q;
    while (m--) {
        cin >> a >> b;
        adj[b].emplace_back(a);
    }
    memset(D, 0xc1, sizeof(D));
    for (int x = 1; x <= n; x++) {
        int sz = adj[x].size();
        vector<int> ix(sz);
        for (int t = 0; t <= sqt; t++) {
            int mx = -1, v, ii;
            for (int i = 0; i < sz; i++) {
                int y = adj[x][i];
                int d = D[y][ix[i]], b = V[y][ix[i]] ;
                if (d + 1 > mx && !vis[b]) mx = d + 1, v = b, ii = i;
            }
            if (mx < 0) {
                D[x][t] = 0; V[x][t] = x;
                break;
            }
            D[x][t] = mx; V[x][t] = v; ix[ii]++;
            vis[b] = 1;
        }
        for (int i = 0; V[x][i]; i++) vis[V[x][i]] = 0;
    }
    while (Q--) {
        cin >> T >> Y;
        vector<int> v(Y);
        for (int& x : v) cin >> x, no[x] = 1;
        if (Y < sqt) {
            for (int j = 0; j <= sqt; j++) {
                if (D[T][j] < 0) {
                    cout << "-1\n";
                    break;
                }
                if (!no[V[T][j]]) {
                    cout << D[T][j] << '\n';
                    break;
                }
            }
        }
        else {
            memset(dp, 0xc1, sizeof(dp));
            int ans = -1;
            dp[T] = 0;
            for (int i = T; i; i--) {
                if (!no[i]) ans = max(ans, dp[i]);
                for (int& j : adj[i]) dp[j] = max(dp[j], dp[i] + 1);
            }
            cout << ans << '\n';
        }
        for (int& x : v) no[x] = 0;
    }
    return 0;
}

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