oj.uz

Submission #111572

# Submission time Handle Problem Language Result Execution time Memory
111572 2019-05-15T15:50:35 Z TAISA_ Bitaro’s Party (JOI18_bitaro) C++14
14 / 100
 2000 ms 147828 KB 
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr double eps = 1e-9;
constexpr ll MOD = 1000000007LL;
template <typename T>
bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
};
template <typename T>
bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
};
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for(int i = 0; i < v.size(); i++) {
        os << v[i] << (i + 1 == v.size() ? "\n" : " ");
    }
    return os;
}
template <typename T>
vector<T> make_v(size_t a) {
    return vector<T>(a);
}
template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) {
    t = v;
}
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) {
    for(auto& e : t) {
        fill_v(e, v);
    }
};
int main() {
    /*cin.tie(0);
    ios::sync_with_stdio(false);
    */
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    vector<int> v, in(n);
    vector<vector<int>> G(n);
    int sq = sqrt(100000) - 150;
    auto dp = make_v<int>(n, sq + 1);
    auto idx = make_v<int>(n, sq + 1);
    fill_v(dp, -INF);
    fill_v(idx, -1);
    vector<int> sz(n), vis(n);
    for(int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        --a;
        --b;
        G[a].push_back(b);
        in[b]++;
    }
    stack<int> st;
    for(int i = 0; i < n; i++) {
        if(in[i] == 0) {
            st.push(i);
        }
        dp[i][0] = 0;
        idx[i][0] = i;
        sz[i] = 1;
    }
    while(!st.empty()) {
        int i = st.top();
        v.push_back(i);
        st.pop();
        for(auto e : G[i]) {
            in[e]--;
            if(in[e] == 0) {
                st.push(e);
            }
        }
    }
    for(auto& i : v) {
        for(auto& e : G[i]) {
            vector<int> ndp(sq + 1, -INF), nid(sq + 1, -1);
            int a = 0, b = 0, t = 0;
            while(a < sz[i] || b < sz[e]) {
                if(t >= sq) {
                    break;
                }
                while(a < sz[i] && vis[idx[i][a]]) {
                    a++;
                }
                while(b < sz[e] && vis[idx[e][b]]) {
                    b++;
                }
                if(a >= sz[i] && b >= sz[e]) {
                    break;
                }
                if(a >= sz[i]) {
                    ndp[t] = dp[e][b];
                    nid[t] = idx[e][b];
                    b++;
                } else if(b >= sz[e] || dp[i][a] + 1 > dp[e][b]) {
                    ndp[t] = dp[i][a] + 1;
                    nid[t] = idx[i][a];
                    a++;
                } else {
                    ndp[t] = dp[e][b];
                    nid[t] = idx[e][b];
                    b++;
                }
                vis[nid[t]] = 1;
                t++;
            }
            sz[e] = t;
            for(int j = 0; j < t; j++) {
                dp[e][j] = ndp[j];
                idx[e][j] = nid[j];
                vis[nid[j]] = 0;
            }
        }
    }
    while(q--) {
        int t, y;
        scanf("%d%d", &t, &y);
        --t;
        vector<int> c(y);
        for(int i = 0; i < y; i++) {
            cin >> c[i];
            --c[i];
            vis[c[i]] = 1;
        }
        int ans = -INF;
        if(y <= sq) {
            for(int i = 0; i <= sq; i++) {
                if(!vis[idx[t][i]]) {
                    ans = dp[t][i];
                    break;
                }
            }
        } else {
            vector<int> dp2(n, -INF);
            for(auto i : v) {
                if(!vis[i]) {
                    chmax(dp2[i], 0);
                }
                for(auto e : G[i]) {
                    chmax(dp2[e], dp2[i] + 1);
                }
            }
            ans = dp2[t];
        }
        printf("%d\n", max(ans, -1));
        for(int i = 0; i < y; i++) {
            vis[c[i]] = 0;
        }
    }
}

Compilation message

bitaro.cpp: In function 'int main()':
bitaro.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:136:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &t, &y);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 7 ms 1792 KB Output is correct
6 Correct 5 ms 1792 KB Output is correct
7 Correct 8 ms 1820 KB Output is correct
8 Correct 8 ms 1792 KB Output is correct
9 Correct 10 ms 1792 KB Output is correct
10 Correct 11 ms 1792 KB Output is correct
11 Correct 7 ms 1792 KB Output is correct
12 Correct 6 ms 1792 KB Output is correct
13 Correct 12 ms 1792 KB Output is correct
14 Correct 8 ms 1792 KB Output is correct
15 Correct 6 ms 1792 KB Output is correct
16 Correct 7 ms 1792 KB Output is correct
17 Correct 7 ms 1792 KB Output is correct
18 Correct 7 ms 1792 KB Output is correct
19 Correct 8 ms 1792 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 7 ms 1792 KB Output is correct
6 Correct 5 ms 1792 KB Output is correct
7 Correct 8 ms 1820 KB Output is correct
8 Correct 8 ms 1792 KB Output is correct
9 Correct 10 ms 1792 KB Output is correct
10 Correct 11 ms 1792 KB Output is correct
11 Correct 7 ms 1792 KB Output is correct
12 Correct 6 ms 1792 KB Output is correct
13 Correct 12 ms 1792 KB Output is correct
14 Correct 8 ms 1792 KB Output is correct
15 Correct 6 ms 1792 KB Output is correct
16 Correct 7 ms 1792 KB Output is correct
17 Correct 7 ms 1792 KB Output is correct
18 Correct 7 ms 1792 KB Output is correct
19 Correct 8 ms 1792 KB Output is correct
20 Correct 430 ms 3016 KB Output is correct
21 Correct 458 ms 2976 KB Output is correct
22 Correct 448 ms 2952 KB Output is correct
23 Correct 470 ms 3024 KB Output is correct
24 Correct 897 ms 146772 KB Output is correct
25 Correct 924 ms 146616 KB Output is correct
26 Correct 886 ms 146552 KB Output is correct
27 Correct 806 ms 147644 KB Output is correct
28 Correct 829 ms 147572 KB Output is correct
29 Correct 899 ms 147572 KB Output is correct
30 Correct 919 ms 146916 KB Output is correct
31 Correct 1040 ms 146844 KB Output is correct
32 Correct 1000 ms 146952 KB Output is correct
33 Correct 811 ms 147476 KB Output is correct
34 Correct 787 ms 147540 KB Output is correct
35 Correct 744 ms 147500 KB Output is correct
36 Correct 860 ms 147652 KB Output is correct
37 Correct 898 ms 147772 KB Output is correct
38 Correct 994 ms 147660 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 7 ms 1792 KB Output is correct
6 Correct 5 ms 1792 KB Output is correct
7 Correct 8 ms 1820 KB Output is correct
8 Correct 8 ms 1792 KB Output is correct
9 Correct 10 ms 1792 KB Output is correct
10 Correct 11 ms 1792 KB Output is correct
11 Correct 7 ms 1792 KB Output is correct
12 Correct 6 ms 1792 KB Output is correct
13 Correct 12 ms 1792 KB Output is correct
14 Correct 8 ms 1792 KB Output is correct
15 Correct 6 ms 1792 KB Output is correct
16 Correct 7 ms 1792 KB Output is correct
17 Correct 7 ms 1792 KB Output is correct
18 Correct 7 ms 1792 KB Output is correct
19 Correct 8 ms 1792 KB Output is correct
20 Correct 430 ms 3016 KB Output is correct
21 Correct 458 ms 2976 KB Output is correct
22 Correct 448 ms 2952 KB Output is correct
23 Correct 470 ms 3024 KB Output is correct
24 Correct 897 ms 146772 KB Output is correct
25 Correct 924 ms 146616 KB Output is correct
26 Correct 886 ms 146552 KB Output is correct
27 Correct 806 ms 147644 KB Output is correct
28 Correct 829 ms 147572 KB Output is correct
29 Correct 899 ms 147572 KB Output is correct
30 Correct 919 ms 146916 KB Output is correct
31 Correct 1040 ms 146844 KB Output is correct
32 Correct 1000 ms 146952 KB Output is correct
33 Correct 811 ms 147476 KB Output is correct
34 Correct 787 ms 147540 KB Output is correct
35 Correct 744 ms 147500 KB Output is correct
36 Correct 860 ms 147652 KB Output is correct
37 Correct 898 ms 147772 KB Output is correct
38 Correct 994 ms 147660 KB Output is correct
39 Correct 1056 ms 146472 KB Output is correct
40 Correct 927 ms 146176 KB Output is correct
41 Correct 1006 ms 146400 KB Output is correct
42 Correct 1900 ms 146564 KB Output is correct
43 Correct 999 ms 146548 KB Output is correct
44 Correct 532 ms 3420 KB Output is correct
45 Correct 464 ms 3068 KB Output is correct
46 Correct 525 ms 2940 KB Output is correct
47 Correct 550 ms 2972 KB Output is correct
48 Correct 570 ms 2972 KB Output is correct
49 Correct 1158 ms 147828 KB Output is correct
50 Correct 978 ms 147324 KB Output is correct
51 Correct 653 ms 3364 KB Output is correct
52 Correct 408 ms 2988 KB Output is correct
53 Correct 1123 ms 147640 KB Output is correct
54 Correct 1148 ms 147432 KB Output is correct
55 Correct 951 ms 147284 KB Output is correct
56 Correct 965 ms 147256 KB Output is correct
57 Correct 616 ms 3444 KB Output is correct
58 Correct 639 ms 3352 KB Output is correct
59 Correct 403 ms 2960 KB Output is correct
60 Correct 417 ms 2972 KB Output is correct
61 Correct 1072 ms 147584 KB Output is correct
62 Correct 1314 ms 147680 KB Output is correct
63 Correct 1844 ms 147780 KB Output is correct
64 Correct 1928 ms 147608 KB Output is correct
65 Execution timed out 2053 ms 147660 KB Time limit exceeded
66 Halted 0 ms 0 KB -