Submission #438390

#	Time	Username	Problem	Language	Result	Execution time	Memory
438390		JovanB	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2001 ms	13312 KiB

bitaro

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

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

const int K = 350;
const int MAXN = 100000;

vector <int> graf[MAXN+5];
vector <int> rgraf[MAXN+5];
bool moze[MAXN+5];
int dp[MAXN+5];
vector <pair <int, int>> dists[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 = 0;
            for(auto x : dists[c]){
                while(j < dists[i].size() && dists[i][j].first >= x.first + 1){
                    temp.push_back(dists[i][j]);
                    j++;
                }
                temp.push_back({x.first + 1, x.second});
            }
            while(j < dists[i].size()){
                temp.push_back(dists[i][j]);
                j++;
            }
            dists[i].clear();
            for(auto c : temp){
                if(dists[i].size() > K) break;
                if(used[c.second]) continue;
                used[c.second] = 1;
                dists[i].push_back({c.first, c.second});
            }
            for(auto c : temp) used[c.second] = 0;
        }
        dists[i].push_back({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(auto c : dists[root]) if(moze[c.second]) mx = max(mx, c.first);
            cout << mx << "\n";
        }
        else{
            cout << resi(root) << "\n";
        }
        for(auto c : vec) moze[c] = 1;
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:50:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |                 while(j < dists[i].size() && dists[i][j].first >= x.first + 1){
      |                       ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             while(j < dists[i].size()){
      |                   ~~^~~~~~~~~~~~~~~~~

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