oj.uz

Submission #111580

# Submission time Handle Problem Language Result Execution time Memory
111580 2019-05-15T16:00:23 Z TAISA_ Bitaro’s Party (JOI18_bitaro) C++14
14 / 100
 2000 ms 169716 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;
    cin >> n >> m >> q;
    vector<int> v, in(n);
    vector<vector<int>> G(n);
    int sq = sqrt(100000) - 120;
    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;
        cin >> 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);
            }
        }
    }
    vector<int> ndp(sq + 1, -INF), nid(sq + 1, -1);
    for(auto& i : v) {
        for(auto& e : G[i]) {
            int a = 0, b = 0, t = 0;
            while(a < sz[i] || b < sz[e]) {
                if(t >= sq) {
                    break;
                }
                bool f = false;
                if(a >= sz[i]) {
                    ndp[t] = dp[e][b];
                    nid[t] = idx[e][b];
                    f = vis[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];
                    f = vis[idx[i][a]];
                    a++;
                } else {
                    ndp[t] = dp[e][b];
                    nid[t] = idx[e][b];
                    f = vis[idx[e][b]];
                    b++;
                }
                if(f) {
                    continue;
                }
                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;
        cin >> 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];
        }
        cout << max(ans, -1) << "\n";
        for(int i = 0; i < y; i++) {
            vis[c[i]] = 0;
        }
    }
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 6 ms 2048 KB Output is correct
6 Correct 5 ms 2048 KB Output is correct
7 Correct 5 ms 2048 KB Output is correct
8 Correct 9 ms 2048 KB Output is correct
9 Correct 10 ms 2048 KB Output is correct
10 Correct 8 ms 2048 KB Output is correct
11 Correct 8 ms 2048 KB Output is correct
12 Correct 6 ms 2048 KB Output is correct
13 Correct 7 ms 2048 KB Output is correct
14 Correct 8 ms 2048 KB Output is correct
15 Correct 5 ms 2048 KB Output is correct
16 Correct 6 ms 2048 KB Output is correct
17 Correct 6 ms 2048 KB Output is correct
18 Correct 5 ms 2048 KB Output is correct
19 Correct 11 ms 2048 KB Output is correct
20 Correct 603 ms 3192 KB Output is correct
21 Correct 496 ms 3192 KB Output is correct
22 Correct 537 ms 3200 KB Output is correct
23 Correct 552 ms 3196 KB Output is correct
24 Correct 937 ms 168736 KB Output is correct
25 Correct 1055 ms 168712 KB Output is correct
26 Correct 947 ms 168680 KB Output is correct
27 Correct 1145 ms 169588 KB Output is correct
28 Correct 1022 ms 169580 KB Output is correct
29 Correct 908 ms 169512 KB Output is correct
30 Correct 973 ms 168940 KB Output is correct
31 Correct 1008 ms 168980 KB Output is correct
32 Correct 972 ms 168872 KB Output is correct
33 Correct 804 ms 169348 KB Output is correct
34 Correct 799 ms 169484 KB Output is correct
35 Correct 831 ms 169448 KB Output is correct
36 Correct 1039 ms 169636 KB Output is correct
37 Correct 999 ms 169628 KB Output is correct
38 Correct 939 ms 169676 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 6 ms 2048 KB Output is correct
6 Correct 5 ms 2048 KB Output is correct
7 Correct 5 ms 2048 KB Output is correct
8 Correct 9 ms 2048 KB Output is correct
9 Correct 10 ms 2048 KB Output is correct
10 Correct 8 ms 2048 KB Output is correct
11 Correct 8 ms 2048 KB Output is correct
12 Correct 6 ms 2048 KB Output is correct
13 Correct 7 ms 2048 KB Output is correct
14 Correct 8 ms 2048 KB Output is correct
15 Correct 5 ms 2048 KB Output is correct
16 Correct 6 ms 2048 KB Output is correct
17 Correct 6 ms 2048 KB Output is correct
18 Correct 5 ms 2048 KB Output is correct
19 Correct 11 ms 2048 KB Output is correct
20 Correct 603 ms 3192 KB Output is correct
21 Correct 496 ms 3192 KB Output is correct
22 Correct 537 ms 3200 KB Output is correct
23 Correct 552 ms 3196 KB Output is correct
24 Correct 937 ms 168736 KB Output is correct
25 Correct 1055 ms 168712 KB Output is correct
26 Correct 947 ms 168680 KB Output is correct
27 Correct 1145 ms 169588 KB Output is correct
28 Correct 1022 ms 169580 KB Output is correct
29 Correct 908 ms 169512 KB Output is correct
30 Correct 973 ms 168940 KB Output is correct
31 Correct 1008 ms 168980 KB Output is correct
32 Correct 972 ms 168872 KB Output is correct
33 Correct 804 ms 169348 KB Output is correct
34 Correct 799 ms 169484 KB Output is correct
35 Correct 831 ms 169448 KB Output is correct
36 Correct 1039 ms 169636 KB Output is correct
37 Correct 999 ms 169628 KB Output is correct
38 Correct 939 ms 169676 KB Output is correct
39 Correct 966 ms 168456 KB Output is correct
40 Correct 869 ms 168160 KB Output is correct
41 Correct 962 ms 168188 KB Output is correct
42 Correct 1303 ms 168408 KB Output is correct
43 Correct 910 ms 168564 KB Output is correct
44 Correct 557 ms 3576 KB Output is correct
45 Correct 616 ms 3292 KB Output is correct
46 Correct 517 ms 3192 KB Output is correct
47 Correct 560 ms 3292 KB Output is correct
48 Correct 485 ms 3192 KB Output is correct
49 Correct 1056 ms 169716 KB Output is correct
50 Correct 953 ms 169200 KB Output is correct
51 Correct 675 ms 3704 KB Output is correct
52 Correct 528 ms 3196 KB Output is correct
53 Correct 1067 ms 169636 KB Output is correct
54 Correct 1110 ms 169504 KB Output is correct
55 Correct 978 ms 169312 KB Output is correct
56 Correct 911 ms 169372 KB Output is correct
57 Correct 706 ms 3576 KB Output is correct
58 Correct 610 ms 3704 KB Output is correct
59 Correct 688 ms 3204 KB Output is correct
60 Correct 547 ms 3216 KB Output is correct
61 Correct 1265 ms 169712 KB Output is correct
62 Correct 1986 ms 169628 KB Output is correct
63 Correct 1925 ms 169588 KB Output is correct
64 Execution timed out 2043 ms 169540 KB Time limit exceeded
65 Halted 0 ms 0 KB -