oj.uz

Submission #111584

# Submission time Handle Problem Language Result Execution time Memory
111584 2019-05-15T16:09:26 Z TAISA_ Bitaro’s Party (JOI18_bitaro) C++14
14 / 100
 2000 ms 94460 KB 
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#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 = 100;
    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;
                }
                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;
            }
        }
    }
    vector<int> dp2(n, -INF);
    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 {
            fill_v(dp2, -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 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 6 ms 1280 KB Output is correct
7 Correct 4 ms 1280 KB Output is correct
8 Correct 6 ms 1280 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 8 ms 1280 KB Output is correct
11 Correct 6 ms 1280 KB Output is correct
12 Correct 6 ms 1280 KB Output is correct
13 Correct 6 ms 1280 KB Output is correct
14 Correct 5 ms 1280 KB Output is correct
15 Correct 5 ms 1280 KB Output is correct
16 Correct 5 ms 1280 KB Output is correct
17 Correct 6 ms 1280 KB Output is correct
18 Correct 8 ms 1280 KB Output is correct
19 Correct 6 ms 1280 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 6 ms 1280 KB Output is correct
7 Correct 4 ms 1280 KB Output is correct
8 Correct 6 ms 1280 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 8 ms 1280 KB Output is correct
11 Correct 6 ms 1280 KB Output is correct
12 Correct 6 ms 1280 KB Output is correct
13 Correct 6 ms 1280 KB Output is correct
14 Correct 5 ms 1280 KB Output is correct
15 Correct 5 ms 1280 KB Output is correct
16 Correct 5 ms 1280 KB Output is correct
17 Correct 6 ms 1280 KB Output is correct
18 Correct 8 ms 1280 KB Output is correct
19 Correct 6 ms 1280 KB Output is correct
20 Correct 247 ms 2416 KB Output is correct
21 Correct 265 ms 2552 KB Output is correct
22 Correct 267 ms 2428 KB Output is correct
23 Correct 254 ms 2552 KB Output is correct
24 Correct 663 ms 93580 KB Output is correct
25 Correct 632 ms 93412 KB Output is correct
26 Correct 595 ms 93400 KB Output is correct
27 Correct 551 ms 94420 KB Output is correct
28 Correct 521 ms 94448 KB Output is correct
29 Correct 565 ms 94440 KB Output is correct
30 Correct 567 ms 93732 KB Output is correct
31 Correct 670 ms 93684 KB Output is correct
32 Correct 576 ms 93812 KB Output is correct
33 Correct 549 ms 94228 KB Output is correct
34 Correct 530 ms 94300 KB Output is correct
35 Correct 515 ms 94348 KB Output is correct
36 Correct 560 ms 94428 KB Output is correct
37 Correct 591 ms 94460 KB Output is correct
38 Correct 611 ms 94432 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 6 ms 1280 KB Output is correct
7 Correct 4 ms 1280 KB Output is correct
8 Correct 6 ms 1280 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 8 ms 1280 KB Output is correct
11 Correct 6 ms 1280 KB Output is correct
12 Correct 6 ms 1280 KB Output is correct
13 Correct 6 ms 1280 KB Output is correct
14 Correct 5 ms 1280 KB Output is correct
15 Correct 5 ms 1280 KB Output is correct
16 Correct 5 ms 1280 KB Output is correct
17 Correct 6 ms 1280 KB Output is correct
18 Correct 8 ms 1280 KB Output is correct
19 Correct 6 ms 1280 KB Output is correct
20 Correct 247 ms 2416 KB Output is correct
21 Correct 265 ms 2552 KB Output is correct
22 Correct 267 ms 2428 KB Output is correct
23 Correct 254 ms 2552 KB Output is correct
24 Correct 663 ms 93580 KB Output is correct
25 Correct 632 ms 93412 KB Output is correct
26 Correct 595 ms 93400 KB Output is correct
27 Correct 551 ms 94420 KB Output is correct
28 Correct 521 ms 94448 KB Output is correct
29 Correct 565 ms 94440 KB Output is correct
30 Correct 567 ms 93732 KB Output is correct
31 Correct 670 ms 93684 KB Output is correct
32 Correct 576 ms 93812 KB Output is correct
33 Correct 549 ms 94228 KB Output is correct
34 Correct 530 ms 94300 KB Output is correct
35 Correct 515 ms 94348 KB Output is correct
36 Correct 560 ms 94428 KB Output is correct
37 Correct 591 ms 94460 KB Output is correct
38 Correct 611 ms 94432 KB Output is correct
39 Correct 720 ms 93608 KB Output is correct
40 Correct 607 ms 93404 KB Output is correct
41 Execution timed out 2056 ms 93408 KB Time limit exceeded
42 Halted 0 ms 0 KB -