oj.uz

Submission #963311

# Submission time Handle Problem Language Result Execution time Memory
963311 2024-04-14T20:41:32 Z TimAni Bitaro’s Party (JOI18_bitaro) C++17
100 / 100
 807 ms 147380 KB 
//start-time: 2024-04-14 19:39:32
#include <bits/stdc++.h>

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);
    vector<int> vis(n), cur(n), val(n);

    for(int u = 0; u < n; u++, cur.clear()){
        for(auto &v : gR[u]){
            for(auto &[value, ind] : dp[v]){
                if(vis[ind] == u) val[ind] = max(val[ind], value + 1);
                else vis[ind] = u, val[ind] = value + 1, cur.push_back(ind);
            }
        }
		for(auto v : cur) dp[u].push_back({val[v],v});
		dp[u].push_back({0,u}); 
        sort(dp[u].rbegin(), dp[u].rend());
		if(dp[u].size()>w) dp[u].erase(dp[u].begin() + w, dp[u].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 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 856 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 3 ms 1372 KB Output is correct
9 Correct 3 ms 1624 KB Output is correct
10 Correct 3 ms 1372 KB Output is correct
11 Correct 3 ms 1372 KB Output is correct
12 Correct 3 ms 1116 KB Output is correct
13 Correct 4 ms 1372 KB Output is correct
14 Correct 3 ms 1116 KB Output is correct
15 Correct 3 ms 868 KB Output is correct
16 Correct 3 ms 1116 KB Output is correct
17 Correct 3 ms 1116 KB Output is correct
18 Correct 3 ms 1116 KB Output is correct
19 Correct 3 ms 1112 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 856 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 3 ms 1372 KB Output is correct
9 Correct 3 ms 1624 KB Output is correct
10 Correct 3 ms 1372 KB Output is correct
11 Correct 3 ms 1372 KB Output is correct
12 Correct 3 ms 1116 KB Output is correct
13 Correct 4 ms 1372 KB Output is correct
14 Correct 3 ms 1116 KB Output is correct
15 Correct 3 ms 868 KB Output is correct
16 Correct 3 ms 1116 KB Output is correct
17 Correct 3 ms 1116 KB Output is correct
18 Correct 3 ms 1116 KB Output is correct
19 Correct 3 ms 1112 KB Output is correct
20 Correct 56 ms 2636 KB Output is correct
21 Correct 57 ms 2628 KB Output is correct
22 Correct 57 ms 2640 KB Output is correct
23 Correct 51 ms 2664 KB Output is correct
24 Correct 519 ms 114588 KB Output is correct
25 Correct 499 ms 110992 KB Output is correct
26 Correct 521 ms 110528 KB Output is correct
27 Correct 288 ms 112328 KB Output is correct
28 Correct 295 ms 112304 KB Output is correct
29 Correct 300 ms 112304 KB Output is correct
30 Correct 322 ms 112224 KB Output is correct
31 Correct 440 ms 130220 KB Output is correct
32 Correct 317 ms 112220 KB Output is correct
33 Correct 262 ms 76404 KB Output is correct
34 Correct 435 ms 103960 KB Output is correct
35 Correct 264 ms 76060 KB Output is correct
36 Correct 316 ms 92960 KB Output is correct
37 Correct 484 ms 114988 KB Output is correct
38 Correct 299 ms 93188 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 856 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 3 ms 1372 KB Output is correct
9 Correct 3 ms 1624 KB Output is correct
10 Correct 3 ms 1372 KB Output is correct
11 Correct 3 ms 1372 KB Output is correct
12 Correct 3 ms 1116 KB Output is correct
13 Correct 4 ms 1372 KB Output is correct
14 Correct 3 ms 1116 KB Output is correct
15 Correct 3 ms 868 KB Output is correct
16 Correct 3 ms 1116 KB Output is correct
17 Correct 3 ms 1116 KB Output is correct
18 Correct 3 ms 1116 KB Output is correct
19 Correct 3 ms 1112 KB Output is correct
20 Correct 56 ms 2636 KB Output is correct
21 Correct 57 ms 2628 KB Output is correct
22 Correct 57 ms 2640 KB Output is correct
23 Correct 51 ms 2664 KB Output is correct
24 Correct 519 ms 114588 KB Output is correct
25 Correct 499 ms 110992 KB Output is correct
26 Correct 521 ms 110528 KB Output is correct
27 Correct 288 ms 112328 KB Output is correct
28 Correct 295 ms 112304 KB Output is correct
29 Correct 300 ms 112304 KB Output is correct
30 Correct 322 ms 112224 KB Output is correct
31 Correct 440 ms 130220 KB Output is correct
32 Correct 317 ms 112220 KB Output is correct
33 Correct 262 ms 76404 KB Output is correct
34 Correct 435 ms 103960 KB Output is correct
35 Correct 264 ms 76060 KB Output is correct
36 Correct 316 ms 92960 KB Output is correct
37 Correct 484 ms 114988 KB Output is correct
38 Correct 299 ms 93188 KB Output is correct
39 Correct 698 ms 116316 KB Output is correct
40 Correct 514 ms 113584 KB Output is correct
41 Correct 746 ms 115212 KB Output is correct
42 Correct 573 ms 114496 KB Output is correct
43 Correct 513 ms 116384 KB Output is correct
44 Correct 214 ms 4740 KB Output is correct
45 Correct 81 ms 3768 KB Output is correct
46 Correct 109 ms 3940 KB Output is correct
47 Correct 72 ms 3452 KB Output is correct
48 Correct 59 ms 3668 KB Output is correct
49 Correct 505 ms 114424 KB Output is correct
50 Correct 586 ms 114212 KB Output is correct
51 Correct 209 ms 4256 KB Output is correct
52 Correct 127 ms 3916 KB Output is correct
53 Correct 481 ms 94668 KB Output is correct
54 Correct 684 ms 115484 KB Output is correct
55 Correct 593 ms 94488 KB Output is correct
56 Correct 807 ms 119180 KB Output is correct
57 Correct 221 ms 4872 KB Output is correct
58 Correct 209 ms 5036 KB Output is correct
59 Correct 128 ms 4432 KB Output is correct
60 Correct 121 ms 4404 KB Output is correct
61 Correct 366 ms 114688 KB Output is correct
62 Correct 389 ms 95636 KB Output is correct
63 Correct 527 ms 115404 KB Output is correct
64 Correct 494 ms 114756 KB Output is correct
65 Correct 465 ms 95124 KB Output is correct
66 Correct 641 ms 117372 KB Output is correct
67 Correct 586 ms 114612 KB Output is correct
68 Correct 583 ms 95684 KB Output is correct
69 Correct 757 ms 117524 KB Output is correct
70 Correct 320 ms 114704 KB Output is correct
71 Correct 337 ms 95320 KB Output is correct
72 Correct 496 ms 117124 KB Output is correct
73 Correct 338 ms 114528 KB Output is correct
74 Correct 341 ms 95412 KB Output is correct
75 Correct 508 ms 119540 KB Output is correct
76 Correct 494 ms 115832 KB Output is correct
77 Correct 571 ms 114888 KB Output is correct
78 Correct 311 ms 114896 KB Output is correct
79 Correct 201 ms 5272 KB Output is correct
80 Correct 112 ms 4256 KB Output is correct
81 Correct 50 ms 3924 KB Output is correct
82 Correct 521 ms 115396 KB Output is correct
83 Correct 691 ms 136804 KB Output is correct
84 Correct 568 ms 114960 KB Output is correct
85 Correct 710 ms 147380 KB Output is correct
86 Correct 340 ms 114840 KB Output is correct
87 Correct 495 ms 136060 KB Output is correct
88 Correct 210 ms 5152 KB Output is correct
89 Correct 204 ms 5264 KB Output is correct
90 Correct 118 ms 4440 KB Output is correct
91 Correct 122 ms 4360 KB Output is correct
92 Correct 51 ms 3924 KB Output is correct
93 Correct 61 ms 3928 KB Output is correct
94 Correct 454 ms 79528 KB Output is correct
95 Correct 678 ms 113728 KB Output is correct
96 Correct 482 ms 78796 KB Output is correct
97 Correct 693 ms 114104 KB Output is correct
98 Correct 281 ms 79076 KB Output is correct
99 Correct 473 ms 110008 KB Output is correct
100 Correct 198 ms 5228 KB Output is correct
101 Correct 204 ms 5328 KB Output is correct
102 Correct 97 ms 4408 KB Output is correct
103 Correct 94 ms 4452 KB Output is correct
104 Correct 54 ms 4072 KB Output is correct
105 Correct 54 ms 4052 KB Output is correct
106 Correct 517 ms 96016 KB Output is correct
107 Correct 677 ms 122184 KB Output is correct
108 Correct 583 ms 95928 KB Output is correct
109 Correct 742 ms 113504 KB Output is correct
110 Correct 304 ms 96076 KB Output is correct
111 Correct 489 ms 118604 KB Output is correct
112 Correct 215 ms 5200 KB Output is correct
113 Correct 198 ms 5460 KB Output is correct
114 Correct 107 ms 4372 KB Output is correct
115 Correct 115 ms 4436 KB Output is correct
116 Correct 59 ms 4004 KB Output is correct
117 Correct 58 ms 4108 KB Output is correct
118 Correct 310 ms 114388 KB Output is correct
119 Correct 325 ms 95200 KB Output is correct
120 Correct 504 ms 122516 KB Output is correct
121 Correct 343 ms 114376 KB Output is correct
122 Correct 315 ms 95000 KB Output is correct
123 Correct 502 ms 121748 KB Output is correct
124 Correct 293 ms 114364 KB Output is correct
125 Correct 307 ms 95480 KB Output is correct
126 Correct 467 ms 117788 KB Output is correct