Submission #1301776

#TimeUsernameProblemLanguageResultExecution timeMemory
1301776kiteyuBitaro’s Party (JOI18_bitaro)C++20
14 / 100
2096 ms7344 KiB
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll = long long;
const int N = 1e5;
const int INF = 1e9;

int n,m,q;
vector<int> adj[N+5];
int d[N+5],qe[N+5],busy[N+5];
bool f[N+5],fbusy[N+5];
int head = 0, tail = 0;
int dlen[N+5],dp[N+5];

vector<pair<int,int>> largest[N+5];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1,x,y; i <= m ; ++i){
        cin >> x >> y;
        adj[y].push_back(x);
    }
    for(int i = 1 ; i <= n ; ++i){
        vector<pair<int,int>> tmp;
        for(int j : adj[i]){
            d[i] = max(d[i],d[j] + 1);
            for(pair<int,int> j1 : largest[j])
                if(j1.se + 1 > dlen[j1.fi]){
                    tmp.push_back({j1.fi,j1.se + 1});
                    dlen[j1.fi] = j1.se + 1;
                }
        }
        tmp.push_back({i,0});

        for(pair<int,int> j : tmp) {
            if(dlen[j.fi] != j.se) largest[i].push_back(j);
        }
        for(pair<int,int> j : tmp)
            dlen[j.fi] = 0;

        sort(largest[i].begin(),largest[i].end(),[&](pair<int,int> x, pair<int,int>y){
            return x.se > y.se;
        });
        while(largest[i].size() > 100) largest[i].pop_back();
    }
//    for(int i = 1 ; i <= n ; ++i){
//        cout << i << ":\n";
//        for(auto j : largest[i]) cout << j.fi << ',' << j.se << '\n';
//
//    }

    for(int i = 1 ; i <= q ; ++i){ int t,k;
        cin >> t >> k;
        for(int j = 1 ; j <= k ; ++j) cin >> busy[j], fbusy[busy[j]] = 1;
        bool ok = false;
        for(pair<int,int> j : largest[t]) if(!fbusy[j.fi]){
//            cout << j.fi << ',' << j.se << '\n';
            cout << j.se << '\n';
            ok = true;
            break;
        }
        if(!ok){
            for(int j = 1 ; j <= t ; ++j){
                if(fbusy[j]) dp[j] = -INF;
                else dp[j] = 0;
                for(int j1 : adj[j]) dp[j] = max(dp[j],dp[j1]+1);
            }
            cout << max(dp[t],-1) << '\n';
        }
        for(int j = 1 ; j <= k ; ++j) fbusy[busy[j]] = 0;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...