oj.uz

Submission #963258

# Submission time Handle Problem Language Result Execution time Memory
963258 2024-04-14T19:34:43 Z TimAni Bitaro’s Party (JOI18_bitaro) C++17
7 / 100
 2000 ms 32340 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;
}

Compilation message

bitaro.cpp: In function 'void solve()':
bitaro.cpp:65:26: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   65 |                     auto [V, I] = *dp[u].begin();
      |                          ^~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 129 ms 19996 KB Output is correct
6 Correct 107 ms 19036 KB Output is correct
7 Correct 107 ms 19008 KB Output is correct
8 Correct 483 ms 32168 KB Output is correct
9 Correct 465 ms 32340 KB Output is correct
10 Correct 495 ms 32096 KB Output is correct
11 Correct 424 ms 31304 KB Output is correct
12 Correct 236 ms 24396 KB Output is correct
13 Correct 431 ms 31136 KB Output is correct
14 Correct 270 ms 22856 KB Output is correct
15 Correct 154 ms 17832 KB Output is correct
16 Correct 255 ms 22692 KB Output is correct
17 Correct 316 ms 26380 KB Output is correct
18 Correct 179 ms 20920 KB Output is correct
19 Correct 347 ms 27112 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 129 ms 19996 KB Output is correct
6 Correct 107 ms 19036 KB Output is correct
7 Correct 107 ms 19008 KB Output is correct
8 Correct 483 ms 32168 KB Output is correct
9 Correct 465 ms 32340 KB Output is correct
10 Correct 495 ms 32096 KB Output is correct
11 Correct 424 ms 31304 KB Output is correct
12 Correct 236 ms 24396 KB Output is correct
13 Correct 431 ms 31136 KB Output is correct
14 Correct 270 ms 22856 KB Output is correct
15 Correct 154 ms 17832 KB Output is correct
16 Correct 255 ms 22692 KB Output is correct
17 Correct 316 ms 26380 KB Output is correct
18 Correct 179 ms 20920 KB Output is correct
19 Correct 347 ms 27112 KB Output is correct
20 Execution timed out 2066 ms 19724 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 129 ms 19996 KB Output is correct
6 Correct 107 ms 19036 KB Output is correct
7 Correct 107 ms 19008 KB Output is correct
8 Correct 483 ms 32168 KB Output is correct
9 Correct 465 ms 32340 KB Output is correct
10 Correct 495 ms 32096 KB Output is correct
11 Correct 424 ms 31304 KB Output is correct
12 Correct 236 ms 24396 KB Output is correct
13 Correct 431 ms 31136 KB Output is correct
14 Correct 270 ms 22856 KB Output is correct
15 Correct 154 ms 17832 KB Output is correct
16 Correct 255 ms 22692 KB Output is correct
17 Correct 316 ms 26380 KB Output is correct
18 Correct 179 ms 20920 KB Output is correct
19 Correct 347 ms 27112 KB Output is correct
20 Execution timed out 2066 ms 19724 KB Time limit exceeded
21 Halted 0 ms 0 KB -