oj.uz

Submission #966668

# Submission time Handle Problem Language Result Execution time Memory
966668 2024-04-20T07:58:09 Z Pring Bitaro’s Party (JOI18_bitaro) C++17
14 / 100
 1942 ms 303992 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2","popcnt","sse4","abm")
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;

const int MXN = 100005, K = 320, INF = 1e9;
int n, m, q;
vector<int> edge[MXN], edge_inv[MXN];
bitset<MXN> b;
int dis[MXN];
vector<pii> w[MXN];

void MERGE(vector<pii> &a, vector<pii> &b, vector<pii> &c) {
    c.clear();
    for (int i = 0, j = 0; i < a.size() || j < b.size(); ) {
        if (i == a.size()) c.push_back(b[j++]);
        else if (j == b.size()) c.push_back(a[i++]);
        else if (a[i].sc < b[i].sc) c.push_back(b[j++]);
        else c.push_back(a[i++]);
    }
}

void DP(int id) {
    vector<pii> a, bb, c;
    a.push_back(mp(id, 0));
    for (auto pre : edge_inv[id]) {
        for (auto [id, len] : w[pre]) bb.push_back(mp(id, len + 1));
        MERGE(a, bb, c);
        a.clear();
        bb.clear();
        for (auto [id, len] : c) {
            if (b[id]) continue;
            a.push_back(mp(id, len));
        }
        while (a.size() > K + 1) a.pop_back();
    }
    w[id] = a;
}

void TS(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) {
    if (v.size() <= K) {
        for (auto [i, x] : w[t]) {
            if (b[i]) continue;
            return x;
        }
        return -1;
    } else {
        TS(t);
        int ans = -1;
        FOR(i, 1, t + 1) {
            if (b[i]) continue;
            ans = max(ans, dis[i]);
        }
        return ans;
    }
    return 0;
}

void miku() {
    cin >> n >> m >> q;
    while (m--) {
        int x, y;
        cin >> x >> y;
        edge[x].push_back(y);
        edge_inv[y].push_back(x);
    }
    FOR(i, 1, n + 1) DP(i);
    while (q--) {
        int t, y;
        vector<int> v;
        cin >> t >> y;
        v.resize(y);
        for (auto &i : v) {
            cin >> i;
            b[i] = true;
        }
        cout << calc(t, v) << '\n';
        for (auto &i : v) {
            b[i] = false;
        }
    }
    // FOR(i, 1, n + 1) {
    //     debug(i);
    //     for (auto &[id, x] : w[i]) debug(id, x);
    // }
}

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

Compilation message

bitaro.cpp: In function 'void MERGE(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
bitaro.cpp:32:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0, j = 0; i < a.size() || j < b.size(); ) {
      |                            ~~^~~~~~~~~~
bitaro.cpp:32:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0, j = 0; i < a.size() || j < b.size(); ) {
      |                                            ~~^~~~~~~~~~
bitaro.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         if (i == a.size()) c.push_back(b[j++]);
      |             ~~^~~~~~~~~~~
bitaro.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         else if (j == b.size()) c.push_back(a[i++]);
      |                  ~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 7768 KB Output is correct
4 Correct 2 ms 7772 KB Output is correct
5 Correct 13 ms 9664 KB Output is correct
6 Correct 10 ms 9308 KB Output is correct
7 Correct 10 ms 9308 KB Output is correct
8 Correct 20 ms 10844 KB Output is correct
9 Correct 20 ms 10844 KB Output is correct
10 Correct 21 ms 10580 KB Output is correct
11 Correct 19 ms 10588 KB Output is correct
12 Correct 12 ms 9708 KB Output is correct
13 Correct 19 ms 10588 KB Output is correct
14 Correct 12 ms 9308 KB Output is correct
15 Correct 8 ms 8536 KB Output is correct
16 Correct 12 ms 9308 KB Output is correct
17 Correct 14 ms 10076 KB Output is correct
18 Correct 9 ms 9048 KB Output is correct
19 Correct 15 ms 10072 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 7768 KB Output is correct
4 Correct 2 ms 7772 KB Output is correct
5 Correct 13 ms 9664 KB Output is correct
6 Correct 10 ms 9308 KB Output is correct
7 Correct 10 ms 9308 KB Output is correct
8 Correct 20 ms 10844 KB Output is correct
9 Correct 20 ms 10844 KB Output is correct
10 Correct 21 ms 10580 KB Output is correct
11 Correct 19 ms 10588 KB Output is correct
12 Correct 12 ms 9708 KB Output is correct
13 Correct 19 ms 10588 KB Output is correct
14 Correct 12 ms 9308 KB Output is correct
15 Correct 8 ms 8536 KB Output is correct
16 Correct 12 ms 9308 KB Output is correct
17 Correct 14 ms 10076 KB Output is correct
18 Correct 9 ms 9048 KB Output is correct
19 Correct 15 ms 10072 KB Output is correct
20 Correct 1626 ms 14028 KB Output is correct
21 Correct 1607 ms 14220 KB Output is correct
22 Correct 1607 ms 13932 KB Output is correct
23 Correct 1603 ms 14028 KB Output is correct
24 Correct 1440 ms 236488 KB Output is correct
25 Correct 1438 ms 235604 KB Output is correct
26 Correct 1440 ms 236024 KB Output is correct
27 Correct 1741 ms 301652 KB Output is correct
28 Correct 1788 ms 301444 KB Output is correct
29 Correct 1737 ms 301392 KB Output is correct
30 Correct 1725 ms 300976 KB Output is correct
31 Correct 1718 ms 293972 KB Output is correct
32 Correct 1748 ms 301136 KB Output is correct
33 Correct 1194 ms 182612 KB Output is correct
34 Correct 1026 ms 148524 KB Output is correct
35 Correct 1170 ms 182700 KB Output is correct
36 Correct 1498 ms 247672 KB Output is correct
37 Correct 1364 ms 224972 KB Output is correct
38 Correct 1483 ms 248112 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 7768 KB Output is correct
4 Correct 2 ms 7772 KB Output is correct
5 Correct 13 ms 9664 KB Output is correct
6 Correct 10 ms 9308 KB Output is correct
7 Correct 10 ms 9308 KB Output is correct
8 Correct 20 ms 10844 KB Output is correct
9 Correct 20 ms 10844 KB Output is correct
10 Correct 21 ms 10580 KB Output is correct
11 Correct 19 ms 10588 KB Output is correct
12 Correct 12 ms 9708 KB Output is correct
13 Correct 19 ms 10588 KB Output is correct
14 Correct 12 ms 9308 KB Output is correct
15 Correct 8 ms 8536 KB Output is correct
16 Correct 12 ms 9308 KB Output is correct
17 Correct 14 ms 10076 KB Output is correct
18 Correct 9 ms 9048 KB Output is correct
19 Correct 15 ms 10072 KB Output is correct
20 Correct 1626 ms 14028 KB Output is correct
21 Correct 1607 ms 14220 KB Output is correct
22 Correct 1607 ms 13932 KB Output is correct
23 Correct 1603 ms 14028 KB Output is correct
24 Correct 1440 ms 236488 KB Output is correct
25 Correct 1438 ms 235604 KB Output is correct
26 Correct 1440 ms 236024 KB Output is correct
27 Correct 1741 ms 301652 KB Output is correct
28 Correct 1788 ms 301444 KB Output is correct
29 Correct 1737 ms 301392 KB Output is correct
30 Correct 1725 ms 300976 KB Output is correct
31 Correct 1718 ms 293972 KB Output is correct
32 Correct 1748 ms 301136 KB Output is correct
33 Correct 1194 ms 182612 KB Output is correct
34 Correct 1026 ms 148524 KB Output is correct
35 Correct 1170 ms 182700 KB Output is correct
36 Correct 1498 ms 247672 KB Output is correct
37 Correct 1364 ms 224972 KB Output is correct
38 Correct 1483 ms 248112 KB Output is correct
39 Correct 1430 ms 230168 KB Output is correct
40 Correct 1459 ms 234312 KB Output is correct
41 Correct 1429 ms 233564 KB Output is correct
42 Correct 1479 ms 232900 KB Output is correct
43 Correct 1429 ms 232484 KB Output is correct
44 Correct 1634 ms 13304 KB Output is correct
45 Correct 1617 ms 12888 KB Output is correct
46 Correct 1617 ms 12984 KB Output is correct
47 Correct 1613 ms 13176 KB Output is correct
48 Correct 1610 ms 12980 KB Output is correct
49 Correct 1942 ms 301852 KB Output is correct
50 Incorrect 1925 ms 303992 KB Output isn't correct
51 Halted 0 ms 0 KB -