oj.uz

Submission #967330

# Submission time Handle Problem Language Result Execution time Memory
967330 2024-04-22T01:50:36 Z Pring Bitaro’s Party (JOI18_bitaro) C++17
14 / 100
 2000 ms 517940 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

namespace {
    const int MXN = 100005, K = 320, INF = 1e9;
    int n, m, q;
    vector<int> edge[MXN], edge_inv[MXN];
    int ns[MXN];
    pii dp[MXN][K * 2];
    pii pd[3][K * 2];
    bitset<MXN> b;
    int dis[MXN];

    void DP(int id) {
        pd[0][0] = mp(0, id);
        int nn = 1, nnn;
        for (auto &pre : edge_inv[id]) {
            debug(id, pre);
            copy(dp[pre], dp[pre] + ns[pre], pd[2]);
            FOR(i, 0, ns[pre]) pd[2][i].fs++;
            merge(pd[0], pd[0] + nn, pd[2], pd[2] + ns[pre], pd[1], greater<pii>());
            nnn = nn + ns[pre];
            nn = 0;
            FOR(i, 0, nnn) {
                if (b[pd[1][i].sc]) continue;
                b[pd[1][i].sc] = true;
                pd[0][nn] = pd[1][i];
                nn++;
            }
            FOR(i, 0, nn) b[pd[0][i].sc] = false;
            nn = min(nn, K);
        }
        copy(pd[0], pd[0] + nn, dp[id]);
        ns[id] = nn;
    }

    void PRE() {
        FOR(i, 1, n + 1) DP(i);
        // FOR(i, 1, n + 1) {
        //     cout << ns[i] << '\n';
        //     FOR(j, 0, ns[i]) cout << '<' << dp[i][j].fs << ' ' << dp[i][j].sc << '>' << ' ';
        //     cout << '\n';
        // }
    }

    void BAO(int sr) {
        fill(dis + 1, dis + n + 1, -INF);
        dis[sr] = 0;
        for (int id = sr - 1; id; id--) {
            for (auto &i : edge[id]) dis[id] = max(dis[id], dis[i] + 1);
        }
    }

    int calc(int t, vector<int> &v) {
        auto DO = [&]() -> int {
            if (t <= K) {
                FOR(i, 0, ns[t]) {
                    auto [w, x] = dp[t][i];
                    if (!b[x]) return w;
                }
                return -1;
            } else {
                BAO(t);
                int ans = -1;
                FOR(i, 1, t + 1) {
                    if (b[i]) continue;
                    ans = max(ans, dis[i]);
                }
                return ans;
            }
        };
        for (auto &i : v) b[i] = true;
        int x = DO();
        for (auto &i : v) b[i] = false;
        return x;
    }
}

vector<int> solve(int N, int M, int Q, vector<int> &S, vector<int> &E, vector<int> &T, vector<vector<int>> &Y) {
    ::n = N;
    ::m = M;
    ::q = Q;
    FOR(i, 0, M) {
        edge[S[i]].push_back(E[i]);
        edge_inv[E[i]].push_back(S[i]);
    }
    PRE();
    vector<int> ans;
    FOR(i, 0, q) {
        ans.push_back(calc(T[i], Y[i]));
    }
    return ans;
}

void miku() {
    int n, m, q;
    vector<vector<int>> y;
    cin >> n >> m >> q;
    vector<int> s(m), e(m);
    FOR(i, 0, m) cin >> s[i] >> e[i];
    vector<int> t(q);
    FOR(i, 0, q) {
        int k;
        cin >> t[i] >> k;
        y.push_back(vector<int>(k));
        for (auto &i : y.back()) cin >> i;
    }
    vector<int> ans = solve(n, m, q, s, e, t, y);
    for (auto &i : ans) cout << i << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Compilation message

bitaro.cpp: In function 'void {anonymous}::DP(int)':
bitaro.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
bitaro.cpp:35:13: note: in expansion of macro 'debug'
   35 |             debug(id, pre);
      |             ^~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8024 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 2 ms 8024 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 4 ms 12124 KB Output is correct
6 Correct 4 ms 12124 KB Output is correct
7 Correct 4 ms 12124 KB Output is correct
8 Correct 7 ms 12120 KB Output is correct
9 Correct 7 ms 12124 KB Output is correct
10 Correct 8 ms 12364 KB Output is correct
11 Correct 6 ms 12124 KB Output is correct
12 Correct 5 ms 12124 KB Output is correct
13 Correct 7 ms 12216 KB Output is correct
14 Correct 6 ms 12124 KB Output is correct
15 Correct 5 ms 12124 KB Output is correct
16 Correct 6 ms 12124 KB Output is correct
17 Correct 8 ms 12376 KB Output is correct
18 Correct 5 ms 12124 KB Output is correct
19 Correct 6 ms 12364 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8024 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 2 ms 8024 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 4 ms 12124 KB Output is correct
6 Correct 4 ms 12124 KB Output is correct
7 Correct 4 ms 12124 KB Output is correct
8 Correct 7 ms 12120 KB Output is correct
9 Correct 7 ms 12124 KB Output is correct
10 Correct 8 ms 12364 KB Output is correct
11 Correct 6 ms 12124 KB Output is correct
12 Correct 5 ms 12124 KB Output is correct
13 Correct 7 ms 12216 KB Output is correct
14 Correct 6 ms 12124 KB Output is correct
15 Correct 5 ms 12124 KB Output is correct
16 Correct 6 ms 12124 KB Output is correct
17 Correct 8 ms 12376 KB Output is correct
18 Correct 5 ms 12124 KB Output is correct
19 Correct 6 ms 12364 KB Output is correct
20 Correct 529 ms 17888 KB Output is correct
21 Correct 426 ms 18004 KB Output is correct
22 Correct 529 ms 17892 KB Output is correct
23 Correct 632 ms 17744 KB Output is correct
24 Correct 711 ms 491088 KB Output is correct
25 Correct 695 ms 493092 KB Output is correct
26 Correct 711 ms 492780 KB Output is correct
27 Correct 746 ms 517784 KB Output is correct
28 Correct 736 ms 517940 KB Output is correct
29 Correct 720 ms 517712 KB Output is correct
30 Correct 659 ms 517180 KB Output is correct
31 Correct 674 ms 517200 KB Output is correct
32 Correct 681 ms 517116 KB Output is correct
33 Correct 590 ms 483824 KB Output is correct
34 Correct 488 ms 475476 KB Output is correct
35 Correct 558 ms 483152 KB Output is correct
36 Correct 658 ms 499556 KB Output is correct
37 Correct 595 ms 495680 KB Output is correct
38 Correct 650 ms 500548 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8024 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 2 ms 8024 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 4 ms 12124 KB Output is correct
6 Correct 4 ms 12124 KB Output is correct
7 Correct 4 ms 12124 KB Output is correct
8 Correct 7 ms 12120 KB Output is correct
9 Correct 7 ms 12124 KB Output is correct
10 Correct 8 ms 12364 KB Output is correct
11 Correct 6 ms 12124 KB Output is correct
12 Correct 5 ms 12124 KB Output is correct
13 Correct 7 ms 12216 KB Output is correct
14 Correct 6 ms 12124 KB Output is correct
15 Correct 5 ms 12124 KB Output is correct
16 Correct 6 ms 12124 KB Output is correct
17 Correct 8 ms 12376 KB Output is correct
18 Correct 5 ms 12124 KB Output is correct
19 Correct 6 ms 12364 KB Output is correct
20 Correct 529 ms 17888 KB Output is correct
21 Correct 426 ms 18004 KB Output is correct
22 Correct 529 ms 17892 KB Output is correct
23 Correct 632 ms 17744 KB Output is correct
24 Correct 711 ms 491088 KB Output is correct
25 Correct 695 ms 493092 KB Output is correct
26 Correct 711 ms 492780 KB Output is correct
27 Correct 746 ms 517784 KB Output is correct
28 Correct 736 ms 517940 KB Output is correct
29 Correct 720 ms 517712 KB Output is correct
30 Correct 659 ms 517180 KB Output is correct
31 Correct 674 ms 517200 KB Output is correct
32 Correct 681 ms 517116 KB Output is correct
33 Correct 590 ms 483824 KB Output is correct
34 Correct 488 ms 475476 KB Output is correct
35 Correct 558 ms 483152 KB Output is correct
36 Correct 658 ms 499556 KB Output is correct
37 Correct 595 ms 495680 KB Output is correct
38 Correct 650 ms 500548 KB Output is correct
39 Execution timed out 2065 ms 497212 KB Time limit exceeded
40 Halted 0 ms 0 KB -