oj.uz

답안 #963226

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
963226 2024-04-14T18:58:52 Z TimAni Bitaro’s Party (JOI18_bitaro) C++17
0 / 100
 894 ms 75600 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);
    for(auto el : topo){
        dp[el].insert({0, el});
        cnt[el][el] = 1;
    }
    
    map<int, map<int, ll>> mp;
    const ll w = round(sqrt(1'000'000)) + 1;

    for(auto u : topo){
        for(auto v : gR[u]){
            for(auto [v, i] : dp[v]){
                cnt[u] |= cnt[v];
                ll o = v + 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(auto ms : dp){
        //for(auto [v, i] : ms){
            //cout << v << ' ' << i << '\n';
        //}
        //cout << endl;
    //}
    //TODO  

    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;
        }

        set<array<ll, 2>> ms = dp[u];
        ll ans = 0;
        for(auto [v, i] : ms){
            if(!c[i]){
                ans = max(ans, v);
            }
        }
        cout << ans << endl;
    }
}

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

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 59 ms 17560 KB Output is correct
6 Correct 64 ms 17672 KB Output is correct
7 Correct 58 ms 17232 KB Output is correct
8 Correct 894 ms 75520 KB Output is correct
9 Correct 875 ms 75600 KB Output is correct
10 Correct 876 ms 75552 KB Output is correct
11 Correct 531 ms 51044 KB Output is correct
12 Correct 163 ms 26812 KB Output is correct
13 Correct 497 ms 48952 KB Output is correct
14 Incorrect 687 ms 48708 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 59 ms 17560 KB Output is correct
6 Correct 64 ms 17672 KB Output is correct
7 Correct 58 ms 17232 KB Output is correct
8 Correct 894 ms 75520 KB Output is correct
9 Correct 875 ms 75600 KB Output is correct
10 Correct 876 ms 75552 KB Output is correct
11 Correct 531 ms 51044 KB Output is correct
12 Correct 163 ms 26812 KB Output is correct
13 Correct 497 ms 48952 KB Output is correct
14 Incorrect 687 ms 48708 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 59 ms 17560 KB Output is correct
6 Correct 64 ms 17672 KB Output is correct
7 Correct 58 ms 17232 KB Output is correct
8 Correct 894 ms 75520 KB Output is correct
9 Correct 875 ms 75600 KB Output is correct
10 Correct 876 ms 75552 KB Output is correct
11 Correct 531 ms 51044 KB Output is correct
12 Correct 163 ms 26812 KB Output is correct
13 Correct 497 ms 48952 KB Output is correct
14 Incorrect 687 ms 48708 KB Output isn't correct
15 Halted 0 ms 0 KB -