oj.uz

Submission #963346

# Submission time Handle Problem Language Result Execution time Memory
963346 2024-04-14T21:13:30 Z TimAni Bitaro’s Party (JOI18_bitaro) C++17
14 / 100
 674 ms 117208 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), val(n);
    for(int u = 0; u < n; u++){
        vector<int> cur;
        for(auto &v : gR[u]){
            for(auto &[value, ind] : dp[v]){
                val[ind] = max(val[ind], value + 1);
                if(vis[ind] != u){
                    vis[ind] = u;
                    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 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 4 ms 856 KB Output is correct
8 Correct 3 ms 1372 KB Output is correct
9 Correct 3 ms 1368 KB Output is correct
10 Correct 3 ms 1372 KB Output is correct
11 Correct 4 ms 1372 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 3 ms 1372 KB Output is correct
14 Correct 3 ms 1116 KB Output is correct
15 Correct 3 ms 856 KB Output is correct
16 Correct 3 ms 1116 KB Output is correct
17 Correct 4 ms 1116 KB Output is correct
18 Correct 5 ms 1116 KB Output is correct
19 Correct 3 ms 1116 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 4 ms 856 KB Output is correct
8 Correct 3 ms 1372 KB Output is correct
9 Correct 3 ms 1368 KB Output is correct
10 Correct 3 ms 1372 KB Output is correct
11 Correct 4 ms 1372 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 3 ms 1372 KB Output is correct
14 Correct 3 ms 1116 KB Output is correct
15 Correct 3 ms 856 KB Output is correct
16 Correct 3 ms 1116 KB Output is correct
17 Correct 4 ms 1116 KB Output is correct
18 Correct 5 ms 1116 KB Output is correct
19 Correct 3 ms 1116 KB Output is correct
20 Correct 95 ms 3936 KB Output is correct
21 Correct 60 ms 3872 KB Output is correct
22 Correct 56 ms 3856 KB Output is correct
23 Correct 70 ms 3928 KB Output is correct
24 Correct 475 ms 102124 KB Output is correct
25 Correct 511 ms 98444 KB Output is correct
26 Correct 444 ms 99036 KB Output is correct
27 Correct 349 ms 113028 KB Output is correct
28 Correct 329 ms 113060 KB Output is correct
29 Correct 346 ms 112976 KB Output is correct
30 Correct 328 ms 112768 KB Output is correct
31 Correct 372 ms 117208 KB Output is correct
32 Correct 336 ms 112980 KB Output is correct
33 Correct 311 ms 76816 KB Output is correct
34 Correct 373 ms 85840 KB Output is correct
35 Correct 304 ms 76688 KB Output is correct
36 Correct 343 ms 93504 KB Output is correct
37 Correct 422 ms 97872 KB Output is correct
38 Correct 336 ms 92760 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 4 ms 856 KB Output is correct
8 Correct 3 ms 1372 KB Output is correct
9 Correct 3 ms 1368 KB Output is correct
10 Correct 3 ms 1372 KB Output is correct
11 Correct 4 ms 1372 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 3 ms 1372 KB Output is correct
14 Correct 3 ms 1116 KB Output is correct
15 Correct 3 ms 856 KB Output is correct
16 Correct 3 ms 1116 KB Output is correct
17 Correct 4 ms 1116 KB Output is correct
18 Correct 5 ms 1116 KB Output is correct
19 Correct 3 ms 1116 KB Output is correct
20 Correct 95 ms 3936 KB Output is correct
21 Correct 60 ms 3872 KB Output is correct
22 Correct 56 ms 3856 KB Output is correct
23 Correct 70 ms 3928 KB Output is correct
24 Correct 475 ms 102124 KB Output is correct
25 Correct 511 ms 98444 KB Output is correct
26 Correct 444 ms 99036 KB Output is correct
27 Correct 349 ms 113028 KB Output is correct
28 Correct 329 ms 113060 KB Output is correct
29 Correct 346 ms 112976 KB Output is correct
30 Correct 328 ms 112768 KB Output is correct
31 Correct 372 ms 117208 KB Output is correct
32 Correct 336 ms 112980 KB Output is correct
33 Correct 311 ms 76816 KB Output is correct
34 Correct 373 ms 85840 KB Output is correct
35 Correct 304 ms 76688 KB Output is correct
36 Correct 343 ms 93504 KB Output is correct
37 Correct 422 ms 97872 KB Output is correct
38 Correct 336 ms 92760 KB Output is correct
39 Incorrect 674 ms 100268 KB Output isn't correct
40 Halted 0 ms 0 KB -