Submission #1031444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031444		vjudge1	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	3 ms	7768 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10,b = 317;

int n,m,q,dp[maxn];
bool ocup[maxn];
vector<int> g[2][maxn];
vector<pair<int,int>> dist[maxn];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m >> q;
    
    for(int i = 1;i <= m;i++){
        int u,v;
        cin >> u >> v;
        g[0][u].push_back(v);
        g[1][v].push_back(u);
    }
    
    memset(dp,-1,sizeof dp);
    
    for(int i = 1;i <= n;i++){
        dist[i].push_back({0,i});
        vector<int> calc;
        for(int v : g[1][i])
            for(auto [d,w] : dist[v]){
                if(dp[w] == -1){
                    calc.push_back(w);
                    dp[w] = d + 1;
                }
                else dp[w] = max(dp[w],d + 1);
            }
        
        for(int j : calc){ 
            dist[i].push_back({dp[j],j});
            dp[j] = -1;
        }
        
        sort(dist[i].begin(),dist[i].end(),greater<>());
        
        while((int) dist[i].size() > b) dist[i].pop_back();
    }
    
    while(q--){
        int l,k,resp = 0;
        
        cin >> l >> k;
        
        vector<int> calc(k + 5);
        
        for(int i = 1;i <= k;i++){
            cin >> calc[i];
            ocup[calc[i]] = 1;
        }
        
        if(k < b){
            for(auto [d,i] : dist[l])
                if(!ocup[i])
                    resp = max(resp,d);
        }
        else{
            for(int u = 1;u <= l;u++)
                dp[u] = 0;
            
            for(int u = l;u > 0;u--){
                for(int v : g[1][u]){
                    dp[v] = max(dp[v],dp[u] + 1);
                    if(!ocup[v]) resp = max(resp,dp[v]);
                }
            }
        }
        
        cout << resp << "\n";
        
        for(int i : calc)
            ocup[i] = 0;
        
    }
    
    return 0;
}

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