oj.uz

Submission #963256

# Submission time Handle Problem Language Result Execution time Memory
963256 2024-04-14T19:33:06 Z TimAni Bitaro’s Party (JOI18_bitaro) C++17
7 / 100
 2000 ms 46432 KB 
//start-time: 2024-04-14 19:39:32
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve(){
    ll n, m, q;
    cin >> n >> m >> q;
    vector<vector<ll>> g(n);
    vector<vector<ll>> gR(n);
    for(ll i = 0; i < m; i++){
        ll u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        gR[v].push_back(u);
    }
    
    vector<ll> vis(n), topo;
    auto dfs = [&](ll u, auto&&dfs) -> void {
        vis[u] = 1;
        for(auto v : g[u]){
            if(!vis[v]){
                dfs(v, dfs);
            }
        }
        vis[u] = 2;
        topo.push_back(u);
    };

    for(int i = 0; i < n; i++){
        if(vis[i] == 0){
            dfs(i, dfs);
        }
    }

    reverse(topo.begin(), topo.end());
    
    vector<set<array<ll, 2>>> dp(n);
    vector<bitset<100'001>> cnt(n);
    map<int, map<int, ll>> mp;
    for(auto el : topo){
        dp[el].insert({0, el});
        mp[el][el] = 0;
        cnt[el][el] = 1;
    }
    
    const ll w = round(sqrt(100000)) + 1;

    for(auto u : topo){
        for(auto v : gR[u]){
            for(auto [val, i] : dp[v]){
                cnt[u] |= cnt[v];
                ll o = val + 1;
                if(mp[u][i]) {
                    o = max(o, mp[u][i]);
                    dp[u].erase({mp[u][i], i});
                }
                
                mp[u][i] = o;
                dp[u].insert({o, i});
                if(dp[u].size() > w){
                    auto [V, I] = *dp[u].begin();
                    dp[u].erase(dp[u].begin());
                    mp[u][I] = 0;
                }
            }
        }
    }

    for(ll i = 0; i < q; i++){
        ll u, y;
        cin >> u >> y;
        u--;
        bitset<100'001> c;
        for(ll j = 0; j < y; j++){
            ll a; cin >> a;
            c[--a] = 1;
        }

        if((cnt[u] & c) == cnt[u]){
            cout << -1 << endl;
            continue;
        }

        ll ans = 0;
        if(y < w){
            set<array<ll, 2>> ms = dp[u];
            for(auto [v, i] : ms){
                if(!c[i]){
                    ans = max(ans, v);
                }
            }
        }
        else{
            vector<int> naive(n);
            for(auto v : topo){
                naive[v] = c[v] ? -1 : 0;
                for(auto el : gR[v]){
                    naive[v] = max(naive[v], naive[el] + (naive[el] != -1));
                }
            }
            ans = naive[u];
        }
        
            //for(auto el : naive){
                //cout << el << ' ';
            //}
            //cout << endl;
        cout << ans << endl;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll T = 1;
    //cin >> T;
    while(T--) solve();
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 356 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 74 ms 17720 KB Output is correct
6 Correct 81 ms 17744 KB Output is correct
7 Correct 71 ms 17232 KB Output is correct
8 Correct 680 ms 46288 KB Output is correct
9 Correct 622 ms 46424 KB Output is correct
10 Correct 686 ms 46432 KB Output is correct
11 Correct 563 ms 42528 KB Output is correct
12 Correct 205 ms 26884 KB Output is correct
13 Correct 566 ms 41288 KB Output is correct
14 Correct 472 ms 32476 KB Output is correct
15 Correct 240 ms 22968 KB Output is correct
16 Correct 436 ms 32084 KB Output is correct
17 Correct 434 ms 34944 KB Output is correct
18 Correct 212 ms 24916 KB Output is correct
19 Correct 486 ms 35380 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 356 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 74 ms 17720 KB Output is correct
6 Correct 81 ms 17744 KB Output is correct
7 Correct 71 ms 17232 KB Output is correct
8 Correct 680 ms 46288 KB Output is correct
9 Correct 622 ms 46424 KB Output is correct
10 Correct 686 ms 46432 KB Output is correct
11 Correct 563 ms 42528 KB Output is correct
12 Correct 205 ms 26884 KB Output is correct
13 Correct 566 ms 41288 KB Output is correct
14 Correct 472 ms 32476 KB Output is correct
15 Correct 240 ms 22968 KB Output is correct
16 Correct 436 ms 32084 KB Output is correct
17 Correct 434 ms 34944 KB Output is correct
18 Correct 212 ms 24916 KB Output is correct
19 Correct 486 ms 35380 KB Output is correct
20 Execution timed out 2059 ms 21856 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 356 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 74 ms 17720 KB Output is correct
6 Correct 81 ms 17744 KB Output is correct
7 Correct 71 ms 17232 KB Output is correct
8 Correct 680 ms 46288 KB Output is correct
9 Correct 622 ms 46424 KB Output is correct
10 Correct 686 ms 46432 KB Output is correct
11 Correct 563 ms 42528 KB Output is correct
12 Correct 205 ms 26884 KB Output is correct
13 Correct 566 ms 41288 KB Output is correct
14 Correct 472 ms 32476 KB Output is correct
15 Correct 240 ms 22968 KB Output is correct
16 Correct 436 ms 32084 KB Output is correct
17 Correct 434 ms 34944 KB Output is correct
18 Correct 212 ms 24916 KB Output is correct
19 Correct 486 ms 35380 KB Output is correct
20 Execution timed out 2059 ms 21856 KB Time limit exceeded
21 Halted 0 ms 0 KB -