oj.uz

Submission #212895

# Submission time Handle Problem Language Result Execution time Memory
212895 2020-03-24T12:59:05 Z dolphingarlic Bitaro’s Party (JOI18_bitaro) C++14
100 / 100
 1604 ms 212732 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target("sse4,avx2,fma,avx")
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

const int L = 200;

vector<int> graph[100001];
vector<pair<int, int>> sqrt_farthest[100001];
int a[100001], dp[100001];
bool bad[100001], in_ret[100001];

inline vector<pair<int, int>> merge(vector<pair<int, int>> X, vector<pair<int, int>> Y) {
    vector<pair<int, int>> ret;
    int xptr = 0;
    for (int yptr = 0; ret.size() <= L && yptr < Y.size() && xptr < X.size(); yptr++) {
        while (xptr < X.size() && X[xptr].second >= Y[yptr].second) {
            if (!in_ret[X[xptr].first]) ret.push_back({X[xptr].first, X[xptr].second + 1});
            in_ret[X[xptr].first] = true;
            xptr++;
        }
        if (!in_ret[Y[yptr].first]) ret.push_back(Y[yptr]);
        in_ret[Y[yptr].first] = true;
    }
    while (xptr < X.size() && ret.size() <= L) {
        if (!in_ret[X[xptr].first]) ret.push_back({X[xptr].first, X[xptr].second + 1});
        in_ret[X[xptr].first] = true;
        xptr++;
    }
    for (pair<int, int> i : ret) in_ret[i.first] = false;
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    FOR(i, 0, m) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }

    FOR(i, 1, n + 1) sqrt_farthest[i] = {{i, 0}};
    FOR(i, 1, n + 1) for (int j : graph[i]) sqrt_farthest[j] = merge(sqrt_farthest[i], sqrt_farthest[j]);

    while (k--) {
        int t, y;
        cin >> t >> y;
        FOR(i, 0, y) {
            cin >> a[i];
            bad[a[i]] = true;
        }

        if (y >= L) {
            FOR(i, 1, n + 1) dp[i] = (bad[i] ? INT_MIN : 0);
            FOR(i, 1, t + 1) for (int j : graph[i]) dp[j] = max(dp[j], dp[i] + 1);
            cout << max(-1, dp[t]) << '\n';
        } else {
            bool can = false;
            for (pair<int, int> i : sqrt_farthest[t]) if (!bad[i.first]) {
                can = true;
                cout << i.second << '\n';
                break;
            }
            if (!can) cout << "-1\n";
        }

        FOR(i, 0, y) bad[a[i]] = false;
    }
    return 0;
}

Compilation message

bitaro.cpp: In function 'std::vector<std::pair<int, int> > merge(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:18:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int yptr = 0; ret.size() <= L && yptr < Y.size() && xptr < X.size(); yptr++) {
                                           ~~~~~^~~~~~~~~~
bitaro.cpp:18:67: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int yptr = 0; ret.size() <= L && yptr < Y.size() && xptr < X.size(); yptr++) {
                                                              ~~~~~^~~~~~~~~~
bitaro.cpp:19:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (xptr < X.size() && X[xptr].second >= Y[yptr].second) {
                ~~~~~^~~~~~~~~~
bitaro.cpp:27:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (xptr < X.size() && ret.size() <= L) {
            ~~~~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 13 ms 5632 KB Output is correct
6 Correct 11 ms 5632 KB Output is correct
7 Correct 10 ms 5504 KB Output is correct
8 Correct 17 ms 7040 KB Output is correct
9 Correct 17 ms 7040 KB Output is correct
10 Correct 16 ms 7040 KB Output is correct
11 Correct 17 ms 6912 KB Output is correct
12 Correct 12 ms 6400 KB Output is correct
13 Correct 15 ms 6912 KB Output is correct
14 Correct 17 ms 6272 KB Output is correct
15 Correct 13 ms 5760 KB Output is correct
16 Correct 14 ms 6144 KB Output is correct
17 Correct 23 ms 6472 KB Output is correct
18 Correct 12 ms 6016 KB Output is correct
19 Correct 16 ms 6528 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 13 ms 5632 KB Output is correct
6 Correct 11 ms 5632 KB Output is correct
7 Correct 10 ms 5504 KB Output is correct
8 Correct 17 ms 7040 KB Output is correct
9 Correct 17 ms 7040 KB Output is correct
10 Correct 16 ms 7040 KB Output is correct
11 Correct 17 ms 6912 KB Output is correct
12 Correct 12 ms 6400 KB Output is correct
13 Correct 15 ms 6912 KB Output is correct
14 Correct 17 ms 6272 KB Output is correct
15 Correct 13 ms 5760 KB Output is correct
16 Correct 14 ms 6144 KB Output is correct
17 Correct 23 ms 6472 KB Output is correct
18 Correct 12 ms 6016 KB Output is correct
19 Correct 16 ms 6528 KB Output is correct
20 Correct 768 ms 9080 KB Output is correct
21 Correct 765 ms 9080 KB Output is correct
22 Correct 762 ms 9080 KB Output is correct
23 Correct 840 ms 9156 KB Output is correct
24 Correct 996 ms 157436 KB Output is correct
25 Correct 987 ms 161400 KB Output is correct
26 Correct 1000 ms 161912 KB Output is correct
27 Correct 1141 ms 212600 KB Output is correct
28 Correct 1158 ms 212732 KB Output is correct
29 Correct 1143 ms 212504 KB Output is correct
30 Correct 1133 ms 211960 KB Output is correct
31 Correct 1111 ms 209012 KB Output is correct
32 Correct 1123 ms 211612 KB Output is correct
33 Correct 845 ms 135600 KB Output is correct
34 Correct 749 ms 117880 KB Output is correct
35 Correct 841 ms 134648 KB Output is correct
36 Correct 1016 ms 175192 KB Output is correct
37 Correct 952 ms 163968 KB Output is correct
38 Correct 1016 ms 175736 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 13 ms 5632 KB Output is correct
6 Correct 11 ms 5632 KB Output is correct
7 Correct 10 ms 5504 KB Output is correct
8 Correct 17 ms 7040 KB Output is correct
9 Correct 17 ms 7040 KB Output is correct
10 Correct 16 ms 7040 KB Output is correct
11 Correct 17 ms 6912 KB Output is correct
12 Correct 12 ms 6400 KB Output is correct
13 Correct 15 ms 6912 KB Output is correct
14 Correct 17 ms 6272 KB Output is correct
15 Correct 13 ms 5760 KB Output is correct
16 Correct 14 ms 6144 KB Output is correct
17 Correct 23 ms 6472 KB Output is correct
18 Correct 12 ms 6016 KB Output is correct
19 Correct 16 ms 6528 KB Output is correct
20 Correct 768 ms 9080 KB Output is correct
21 Correct 765 ms 9080 KB Output is correct
22 Correct 762 ms 9080 KB Output is correct
23 Correct 840 ms 9156 KB Output is correct
24 Correct 996 ms 157436 KB Output is correct
25 Correct 987 ms 161400 KB Output is correct
26 Correct 1000 ms 161912 KB Output is correct
27 Correct 1141 ms 212600 KB Output is correct
28 Correct 1158 ms 212732 KB Output is correct
29 Correct 1143 ms 212504 KB Output is correct
30 Correct 1133 ms 211960 KB Output is correct
31 Correct 1111 ms 209012 KB Output is correct
32 Correct 1123 ms 211612 KB Output is correct
33 Correct 845 ms 135600 KB Output is correct
34 Correct 749 ms 117880 KB Output is correct
35 Correct 841 ms 134648 KB Output is correct
36 Correct 1016 ms 175192 KB Output is correct
37 Correct 952 ms 163968 KB Output is correct
38 Correct 1016 ms 175736 KB Output is correct
39 Correct 1042 ms 157968 KB Output is correct
40 Correct 985 ms 159232 KB Output is correct
41 Correct 976 ms 159732 KB Output is correct
42 Correct 1148 ms 159800 KB Output is correct
43 Correct 1008 ms 158764 KB Output is correct
44 Correct 812 ms 9376 KB Output is correct
45 Correct 802 ms 8988 KB Output is correct
46 Correct 783 ms 9080 KB Output is correct
47 Correct 827 ms 9080 KB Output is correct
48 Correct 784 ms 8988 KB Output is correct
49 Correct 1204 ms 211652 KB Output is correct
50 Correct 1117 ms 210468 KB Output is correct
51 Correct 798 ms 8544 KB Output is correct
52 Correct 772 ms 8160 KB Output is correct
53 Correct 1071 ms 174332 KB Output is correct
54 Correct 992 ms 163540 KB Output is correct
55 Correct 1002 ms 173980 KB Output is correct
56 Correct 949 ms 163832 KB Output is correct
57 Correct 821 ms 8592 KB Output is correct
58 Correct 809 ms 8604 KB Output is correct
59 Correct 787 ms 8232 KB Output is correct
60 Correct 826 ms 8252 KB Output is correct
61 Correct 1280 ms 210864 KB Output is correct
62 Correct 1239 ms 175108 KB Output is correct
63 Correct 1184 ms 162996 KB Output is correct
64 Correct 1604 ms 210884 KB Output is correct
65 Correct 1554 ms 174484 KB Output is correct
66 Correct 1453 ms 164420 KB Output is correct
67 Correct 1551 ms 210912 KB Output is correct
68 Correct 1462 ms 175224 KB Output is correct
69 Correct 1387 ms 162252 KB Output is correct
70 Correct 1147 ms 210980 KB Output is correct
71 Correct 1061 ms 174944 KB Output is correct
72 Correct 1028 ms 163812 KB Output is correct
73 Correct 1250 ms 210972 KB Output is correct
74 Correct 1120 ms 174844 KB Output is correct
75 Correct 1075 ms 163516 KB Output is correct
76 Correct 1211 ms 211424 KB Output is correct
77 Correct 1168 ms 211000 KB Output is correct
78 Correct 1168 ms 211192 KB Output is correct
79 Correct 789 ms 8588 KB Output is correct
80 Correct 761 ms 8240 KB Output is correct
81 Correct 764 ms 8184 KB Output is correct
82 Correct 1148 ms 210556 KB Output is correct
83 Correct 1153 ms 207448 KB Output is correct
84 Correct 1235 ms 210516 KB Output is correct
85 Correct 1191 ms 208768 KB Output is correct
86 Correct 1155 ms 212064 KB Output is correct
87 Correct 1202 ms 209304 KB Output is correct
88 Correct 841 ms 9976 KB Output is correct
89 Correct 816 ms 9976 KB Output is correct
90 Correct 789 ms 9720 KB Output is correct
91 Correct 807 ms 9592 KB Output is correct
92 Correct 785 ms 9592 KB Output is correct
93 Correct 793 ms 9624 KB Output is correct
94 Correct 898 ms 137824 KB Output is correct
95 Correct 815 ms 119620 KB Output is correct
96 Correct 880 ms 136312 KB Output is correct
97 Correct 815 ms 120760 KB Output is correct
98 Correct 872 ms 136952 KB Output is correct
99 Correct 796 ms 120436 KB Output is correct
100 Correct 875 ms 10092 KB Output is correct
101 Correct 862 ms 10076 KB Output is correct
102 Correct 858 ms 9720 KB Output is correct
103 Correct 847 ms 9652 KB Output is correct
104 Correct 860 ms 9644 KB Output is correct
105 Correct 849 ms 9720 KB Output is correct
106 Correct 1044 ms 176888 KB Output is correct
107 Correct 1014 ms 166264 KB Output is correct
108 Correct 1066 ms 176956 KB Output is correct
109 Correct 998 ms 164864 KB Output is correct
110 Correct 1033 ms 177224 KB Output is correct
111 Correct 961 ms 165736 KB Output is correct
112 Correct 806 ms 10104 KB Output is correct
113 Correct 838 ms 10132 KB Output is correct
114 Correct 781 ms 9592 KB Output is correct
115 Correct 780 ms 9592 KB Output is correct
116 Correct 783 ms 9632 KB Output is correct
117 Correct 778 ms 9720 KB Output is correct
118 Correct 1147 ms 211896 KB Output is correct
119 Correct 1043 ms 176356 KB Output is correct
120 Correct 968 ms 164452 KB Output is correct
121 Correct 1125 ms 212108 KB Output is correct
122 Correct 1000 ms 175700 KB Output is correct
123 Correct 931 ms 164344 KB Output is correct
124 Correct 1149 ms 212056 KB Output is correct
125 Correct 1016 ms 176856 KB Output is correct
126 Correct 955 ms 164356 KB Output is correct