Submission #1106980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106980		TrendBattles	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1220 ms	160584 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;
const int BLOCK_SIZE = 100;
 
pair <int, int> maximum[MAX_N][BLOCK_SIZE];
int cnt_max[MAX_N];
vector <pair <int, int>> temp_maximum[MAX_N];
 
vector <int> graph[MAX_N], rev_graph[MAX_N];
int appear[MAX_N];
void Init(int N) {
    for (int i = 0; i < N; ++i) {
        sort(temp_maximum[i].begin(), temp_maximum[i].end(), greater <pair <int, int>> ());
 
        temp_maximum[i].emplace_back(0, i);
        for (pair <int, int>& E : temp_maximum[i]) {
            if (appear[E.second]) continue;
 
            maximum[i][cnt_max[i]++] = E;
            appear[E.second] = true;
            if (cnt_max[i] == BLOCK_SIZE) break;
        }
 
        temp_maximum[i].clear();
        temp_maximum[i].shrink_to_fit();
 
        for (int j = 0; j < cnt_max[i]; ++j) {
            appear[maximum[i][j].second] = false;
 
            for (int v : graph[i]) {
                temp_maximum[v].emplace_back(maximum[i][j].first + 1, maximum[i][j].second);
            }
        }
    }
 
    memset(appear, 1, sizeof appear);
}
 
int dp[MAX_N];
int Brute_Force(int s) {
    int ans = -1;
    memset(dp, -0x3f, sizeof (int) * (s + 1));
 
    dp[s] = 0;
    for (int u = s; u >= 0; --u) {
        if (appear[u]) ans = max(ans, dp[u]);
        
        for (int v : rev_graph[u]) {
            dp[v] = max(dp[v], dp[u] + 1);
        }
    }
 
    return ans;
}
 
int Check_Store(int s) {
    for (int i = 0; i < cnt_max[s]; ++i) {
        if (appear[maximum[s][i].second]) return maximum[s][i].first;
    }
 
    return -1;
}
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 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;
        }
 
        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:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen(INFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
bitaro.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(OUTFILE, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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