oj.uz

Submission #963315

# Submission time Handle Problem Language Result Execution time Memory
963315 2024-04-14T20:44:00 Z TimAni Bitaro’s Party (JOI18_bitaro) C++17
14 / 100
 2000 ms 90748 KB 
//start-time: 2024-04-14 19:39:32
#include <vector>
#include <set>
#include <iostream>
#include <cassert>
#include <algorithm>
 
using namespace std;
using ll = long long;
 
const int w = 100;
 
void solve(){
    int n, m, q;
    cin >> n >> m >> q;
 
    vector<vector<int>> gR(n);
 
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        gR[v - 1].push_back(u - 1);
    }
    
    vector<vector<pair<int, int>>> dp(n);
 
    for(int u = 0; u < n; u++){
        vector<int> val(n, -1);
        set<pair<int, int>> aux;
        aux.insert({0, u});
 
        for(auto &v : gR[u]){
            for(auto &[value, ind] : dp[v]){
                val[ind] = max(val[ind], value + 1);
            }
        }
 
        for(auto &v : gR[u]){
            for(auto &[value, ind] : dp[v]){
                aux.insert({val[ind], ind});
                if(aux.size() > w){
                    aux.erase(aux.begin());
                }
            }
        }
 
        dp[u] = vector<pair<int, int>>(aux.begin(), aux.end());
    }
 
    while(q--){
        vector<bool> c(n);
        int u, y, ans = -1;
        cin >> u >> y;
        u--;
        for(int j = 0; j < y; j++){
            int a; cin >> a;
            c[--a] = 1;
        }
 
        if(y < w) {
            for(auto &[v, i] : dp[u]){
                if(!c[i]){
                    ans = max(ans, v);
                }
            }
        }
        else {
            vector<int> naive(n);
            for(int v = 0; v <= u; v++){
                naive[v] = c[v] ? -1 : 0;
                for(auto &el : gR[v]){
                    naive[v] = max(naive[v], naive[el] + (naive[el] != -1));
                }
            }
            ans = naive[u];
        }
 
        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 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 860 KB Output is correct
6 Correct 7 ms 860 KB Output is correct
7 Correct 6 ms 604 KB Output is correct
8 Correct 8 ms 1116 KB Output is correct
9 Correct 8 ms 1116 KB Output is correct
10 Correct 9 ms 1264 KB Output is correct
11 Correct 10 ms 1300 KB Output is correct
12 Correct 12 ms 860 KB Output is correct
13 Correct 12 ms 1116 KB Output is correct
14 Correct 8 ms 860 KB Output is correct
15 Correct 8 ms 720 KB Output is correct
16 Correct 8 ms 856 KB Output is correct
17 Correct 11 ms 860 KB Output is correct
18 Correct 9 ms 860 KB Output is correct
19 Correct 10 ms 1116 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 860 KB Output is correct
6 Correct 7 ms 860 KB Output is correct
7 Correct 6 ms 604 KB Output is correct
8 Correct 8 ms 1116 KB Output is correct
9 Correct 8 ms 1116 KB Output is correct
10 Correct 9 ms 1264 KB Output is correct
11 Correct 10 ms 1300 KB Output is correct
12 Correct 12 ms 860 KB Output is correct
13 Correct 12 ms 1116 KB Output is correct
14 Correct 8 ms 860 KB Output is correct
15 Correct 8 ms 720 KB Output is correct
16 Correct 8 ms 856 KB Output is correct
17 Correct 11 ms 860 KB Output is correct
18 Correct 9 ms 860 KB Output is correct
19 Correct 10 ms 1116 KB Output is correct
20 Correct 374 ms 3512 KB Output is correct
21 Correct 366 ms 3256 KB Output is correct
22 Correct 376 ms 3412 KB Output is correct
23 Correct 411 ms 3428 KB Output is correct
24 Correct 1855 ms 70952 KB Output is correct
25 Correct 1947 ms 72128 KB Output is correct
26 Correct 1819 ms 71892 KB Output is correct
27 Correct 1422 ms 90740 KB Output is correct
28 Correct 1460 ms 90748 KB Output is correct
29 Correct 1401 ms 90656 KB Output is correct
30 Correct 1625 ms 90544 KB Output is correct
31 Correct 1614 ms 88956 KB Output is correct
32 Correct 1683 ms 90632 KB Output is correct
33 Correct 1256 ms 61008 KB Output is correct
34 Correct 1413 ms 55196 KB Output is correct
35 Correct 1250 ms 60600 KB Output is correct
36 Correct 1342 ms 75604 KB Output is correct
37 Correct 1708 ms 71920 KB Output is correct
38 Correct 1423 ms 76084 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 860 KB Output is correct
6 Correct 7 ms 860 KB Output is correct
7 Correct 6 ms 604 KB Output is correct
8 Correct 8 ms 1116 KB Output is correct
9 Correct 8 ms 1116 KB Output is correct
10 Correct 9 ms 1264 KB Output is correct
11 Correct 10 ms 1300 KB Output is correct
12 Correct 12 ms 860 KB Output is correct
13 Correct 12 ms 1116 KB Output is correct
14 Correct 8 ms 860 KB Output is correct
15 Correct 8 ms 720 KB Output is correct
16 Correct 8 ms 856 KB Output is correct
17 Correct 11 ms 860 KB Output is correct
18 Correct 9 ms 860 KB Output is correct
19 Correct 10 ms 1116 KB Output is correct
20 Correct 374 ms 3512 KB Output is correct
21 Correct 366 ms 3256 KB Output is correct
22 Correct 376 ms 3412 KB Output is correct
23 Correct 411 ms 3428 KB Output is correct
24 Correct 1855 ms 70952 KB Output is correct
25 Correct 1947 ms 72128 KB Output is correct
26 Correct 1819 ms 71892 KB Output is correct
27 Correct 1422 ms 90740 KB Output is correct
28 Correct 1460 ms 90748 KB Output is correct
29 Correct 1401 ms 90656 KB Output is correct
30 Correct 1625 ms 90544 KB Output is correct
31 Correct 1614 ms 88956 KB Output is correct
32 Correct 1683 ms 90632 KB Output is correct
33 Correct 1256 ms 61008 KB Output is correct
34 Correct 1413 ms 55196 KB Output is correct
35 Correct 1250 ms 60600 KB Output is correct
36 Correct 1342 ms 75604 KB Output is correct
37 Correct 1708 ms 71920 KB Output is correct
38 Correct 1423 ms 76084 KB Output is correct
39 Execution timed out 2021 ms 71588 KB Time limit exceeded
40 Halted 0 ms 0 KB -