Submission #438399

#	Time	Username	Problem	Language	Result	Execution time	Memory
438399		JovanB	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1840 ms	227780 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int K = 250;
const int MAXN = 100000;

vector <int> graf[MAXN+5];
vector <int> rgraf[MAXN+5];
bool moze[MAXN+5];
int dp[MAXN+5];
pair <int, int> dists[MAXN+5][K+20];
int sz[MAXN+5];
bool used[MAXN+5];

int n;

int resi(int root){
    for(int i=1; i<=n; i++) dp[i] = -1;
    int mx = -1;
    for(int i=root; i>=1; i--){
        dp[i] = -n;
        if(i == root) dp[i] = 0;
        for(auto c : rgraf[i]) if(c <= root) dp[i] = max(dp[i], dp[c] + 1);
        if(moze[i]) mx = max(mx, dp[i]);
    }
    return mx;
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int m, qr;
    cin >> n >> m >> qr;
    for(int i=1; i<=m; i++){
        int a, b;
        cin >> a >> b;
        graf[b].push_back(a);
        rgraf[a].push_back(b);
    }
    for(int i=1; i<=n; i++) moze[i] = 1;
    for(int i=1; i<=n; i++){
        for(auto c : graf[i]){
            vector <pair <int, int>> temp;
            int j = 1;
            for(int k=1; k<=sz[c]; k++){
                pair <int, int> x = dists[c][k];
                while(j <= sz[i] && dists[i][j].first >= x.first + 1){
                    temp.push_back(dists[i][j]);
                    j++;
                }
                temp.push_back({x.first + 1, x.second});
            }
            while(j <= sz[i]){
                temp.push_back(dists[i][j]);
                j++;
            }
            sz[i] = 0;
            for(auto c : temp){
                if(sz[i] > K) break;
                if(used[c.second]) continue;
                used[c.second] = 1;
                dists[i][++sz[i]] = {c.first, c.second};
            }
            for(auto c : temp) used[c.second] = 0;
        }
        dists[i][++sz[i]] = {0, i};
    }
    for(int qrr=1; qrr<=qr; qrr++){
        int root;
        cin >> root;
        int cnt;
        cin >> cnt;
        vector <int> vec;
        for(int i=1; i<=cnt; i++){
            int x;
            cin >> x;
            vec.push_back(x);
            moze[x] = 0;
        }
        if(cnt <= K){
            int mx = -1;
            for(int k=1; k<=sz[root]; k++) if(moze[dists[root][k].second]) mx = max(mx, dists[root][k].first);
            cout << mx << "\n";
        }
        else{
            cout << resi(root) << "\n";
        }
        for(auto c : vec) moze[c] = 1;
    }
    return 0;
}

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