Submission #130054

#	Time	Username	Problem	Language	Result	Execution time	Memory
130054		doowey	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2079 ms	244636 KiB

bitaro

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;
 
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 9;
const int K = 205;

vector<pii> best[N];
vector<int> T[N];

int dp[N];

vector<pii> unite(vector<pii> a, vector<pii> b){
    vector<pii> res;
    for(auto p : a)
        res.push_back(p);
    for(auto p : b)
        res.push_back(mp(p.fi + 1, p.se));
    sort(res.begin(), res.end());
    reverse(res.begin(), res.end());
    while(res.size() > K) res.pop_back();
    return res;
}

int deg[N];
bool ban[N];

int main(){
    fastIO;
    int n, m, q;
    cin >> n >> m >> q;
    int u[m], v[m];
    for(int i = 0 ; i < m ; i ++ ){
        cin >> u[i] >> v[i];
        T[v[i]].push_back(u[i]);
    }
    for(int i = 1; i <= n; i ++ ){
        best[i].push_back(mp(0, i));
        for(auto p : T[i]){
            best[i] = unite(best[i], best[p]);
        }
    }
    int x, k, y;
    int res;
    for(int i = 0 ;i < q; i ++ ){
        cin >> x >> k;
        vector<int> id;
        if(k >= K-2){
            for(int j = 0 ; j < k ;j  ++ ){
                cin >> y;
                id.push_back(y);
                ban[y] = true;
            }
            int res = -1;
            for(int j = 1; j <= n; j ++ ){
                dp[j] = -17214712;
            }
            dp[x] = 0;
            for(int j = n; j >= 1; j -- ){
                for(auto p : T[j]){
                    dp[p] = max(dp[p], dp[j] + 1);
                }
            }
            for(int j = 1; j <= n; j ++ ){
                if(ban[j]) continue;
                res = max(res, dp[j]);
            }
            cout << res << "\n";
        }
        else{
            for(int j = 0 ; j < k ; j ++ ){
                cin >> y;
                ban[y] = true;
                id.push_back(y);
            }
            res = -1;
            for(auto p : best[x]){
                if(ban[p.se]) continue;
                res = max(res, p.fi);
            }
            cout << res << "\n";
        }
        for(auto p : id)
            ban[p] = false;
    }
    return 0;
}

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