Submission #1106965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106965		TrendBattles	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2037 ms	19176 KiB

bitaro

//https://oj.uz/problem/view/JOI18_bitaro
#include <bits/stdc++.h>
using namespace std;
using lli = int64_t;

#define INFILE "JOI18_bitaro.inp"
#define OUTFILE "JOI18_bitaro.out"

const int MAX_N = (int) 1e5;

vector <int> graph[MAX_N], rev_graph[MAX_N];
int appear[MAX_N];

int dp[MAX_N];
const int inf_32 = 0x3f3f3f3f;

int DP(int u, int dest) {
    if (u == dest) return 0;

    int& now = dp[u];
    if (now != -1) return now;

    now = -inf_32;

    for (int v : graph[u]) {
        now = max(now, DP(v, dest) + 1);
    }
    return now;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen(INFILE, "r")) {
        freopen(INFILE, "r", stdin);
        freopen(OUTFILE, "w", stdout);
    }

    int N, M, Q; cin >> N >> M >> Q;
    for (int i = 0; i < M; ++i) {
        int u, v; cin >> u >> v;
        u -= 1; v -= 1;
        graph[u].push_back(v);
        rev_graph[v].push_back(u);
    }

    // Init(N);
    for (int i = 0; i < N; ++i) appear[i] = true;

    for (int qu = 0; qu < Q; ++qu) {
        int dest, num_busy; cin >> dest >> num_busy;
        dest -= 1;
        vector <int> L(num_busy);
        for (int& x : L) {
            cin >> x;
            x -= 1;

            appear[x] = false;
        }

        int ans = -1;
        memset(dp, -1, sizeof dp);
        for (int i = 0; i < N; ++i) {
            if (appear[i]) ans = max(ans, DP(i, dest));
        }

        cout << ans << '\n';
        // cout << Brute_Force(dest) << '\n';
        // if (num_busy >= BLOCK_SIZE) {
        //     cout << Brute_Force(dest) << '\n';
        // } else {
        //     cout << Check_Store(dest) << '\n';
        // }   

        for (int x : L) {
            appear[x] = true;
        }
    }   
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen(INFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
bitaro.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen(OUTFILE, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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