oj.uz

Submission #1095967

# Submission time Handle Problem Language Result Execution time Memory
1095967 2024-10-03T13:43:09 Z mohammad86 Bitaro’s Party (JOI18_bitaro) C++17
14 / 100
 479 ms 219860 KB 
// https://oj.uz/problem/view/JOI18_bitaro

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 100;
const int sqrtn = 250;
const int inf = 1e9;
int n, m, q;
vector<int> adj[maxn];
vector<int> readj[maxn];
vector<pii> fv[maxn];
int pointer[maxn];
int dis[maxn];
bool mark[maxn];

int main () {
    ios_base::sync_with_stdio(false);

    cin >> n >> m >> q;

    for (int i = 1; i <= m; i++) {
        int s, e;
        cin >> s >> e;
        adj[s].push_back(e);
        readj[e].push_back(s);
    }

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w < sqrtn; w++) {
            int maximum = -1;
            int v = -1;
            int nv = -1;
            for (int j : readj[i]) {
                if (fv[j].size() > pointer[j]) {
                    if (fv[j][pointer[j]].first +1 > maximum) {
                        maximum = fv[j][pointer[j]].first +1;
                        v = fv[j][pointer[j]].second;
                        nv = j;
                    }
                }
            }
            if (v == -1)
                break;
            fv[i].push_back({maximum, v});
            pointer[nv]++;
        }
        for (int j : readj[i])
            pointer[j] = 0;
        fv[i].push_back({0, i});
    }
    vector<int> tmp;

    for (int _ = 1; _ <= q; _++) {
        int t, y;
        cin >> t >> y;
        tmp.clear();
        for (int i = 0; i < y; i++) {
            int c;
            cin >> c;
            tmp.push_back(c);
            mark[c] = true;
        }
        if (y < sqrtn) {
            bool is_find = false;
            for (pii i : fv[t]) {
                if (!mark[i.second]) {
                    cout << i.first << endl;
                    is_find = true;
                    break;
                }
            }
            if (!is_find) {
                cout << -1 << endl;
            }
        } else {
            fill(dis, dis+n+2, -1 * inf);

            dis[t] = 0;

            for (int i = t; i >= 1; i--) {
                for (int j : readj[i]) {
                    dis[j] = max(dis[j], dis[i]+1);
                }
            }

            int ans = -1;
            for (int i= 1; i <= t; i++) {
                if (!mark[i]) {
                    ans = max(ans, dis[i]);
                }
            }
            cout << ans << endl;
        }
        for (int i = 0; i < y; i++) {
            mark[tmp[i]] = false;
        }
    }
}

Compilation message

bitaro.cpp: In function 'int main()':
bitaro.cpp:36:34: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |                 if (fv[j].size() > pointer[j]) {
      |                     ~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 5 ms 7516 KB Output is correct
4 Correct 3 ms 7368 KB Output is correct
5 Correct 7 ms 8796 KB Output is correct
6 Correct 6 ms 8796 KB Output is correct
7 Correct 6 ms 8796 KB Output is correct
8 Correct 8 ms 9564 KB Output is correct
9 Correct 9 ms 9564 KB Output is correct
10 Correct 10 ms 9564 KB Output is correct
11 Correct 8 ms 9300 KB Output is correct
12 Correct 7 ms 9052 KB Output is correct
13 Correct 8 ms 9564 KB Output is correct
14 Correct 6 ms 8540 KB Output is correct
15 Correct 5 ms 8144 KB Output is correct
16 Correct 5 ms 8540 KB Output is correct
17 Correct 6 ms 9052 KB Output is correct
18 Correct 5 ms 8536 KB Output is correct
19 Correct 5 ms 9052 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 5 ms 7516 KB Output is correct
4 Correct 3 ms 7368 KB Output is correct
5 Correct 7 ms 8796 KB Output is correct
6 Correct 6 ms 8796 KB Output is correct
7 Correct 6 ms 8796 KB Output is correct
8 Correct 8 ms 9564 KB Output is correct
9 Correct 9 ms 9564 KB Output is correct
10 Correct 10 ms 9564 KB Output is correct
11 Correct 8 ms 9300 KB Output is correct
12 Correct 7 ms 9052 KB Output is correct
13 Correct 8 ms 9564 KB Output is correct
14 Correct 6 ms 8540 KB Output is correct
15 Correct 5 ms 8144 KB Output is correct
16 Correct 5 ms 8540 KB Output is correct
17 Correct 6 ms 9052 KB Output is correct
18 Correct 5 ms 8536 KB Output is correct
19 Correct 5 ms 9052 KB Output is correct
20 Correct 113 ms 13396 KB Output is correct
21 Correct 94 ms 13396 KB Output is correct
22 Correct 99 ms 13396 KB Output is correct
23 Correct 100 ms 13484 KB Output is correct
24 Correct 340 ms 175824 KB Output is correct
25 Correct 329 ms 175568 KB Output is correct
26 Correct 332 ms 175576 KB Output is correct
27 Correct 344 ms 219604 KB Output is correct
28 Correct 354 ms 219860 KB Output is correct
29 Correct 343 ms 219736 KB Output is correct
30 Correct 340 ms 218980 KB Output is correct
31 Correct 350 ms 214932 KB Output is correct
32 Correct 352 ms 218812 KB Output is correct
33 Correct 254 ms 141260 KB Output is correct
34 Correct 253 ms 122572 KB Output is correct
35 Correct 277 ms 140404 KB Output is correct
36 Correct 335 ms 181208 KB Output is correct
37 Correct 329 ms 170200 KB Output is correct
38 Correct 346 ms 181448 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 5 ms 7516 KB Output is correct
4 Correct 3 ms 7368 KB Output is correct
5 Correct 7 ms 8796 KB Output is correct
6 Correct 6 ms 8796 KB Output is correct
7 Correct 6 ms 8796 KB Output is correct
8 Correct 8 ms 9564 KB Output is correct
9 Correct 9 ms 9564 KB Output is correct
10 Correct 10 ms 9564 KB Output is correct
11 Correct 8 ms 9300 KB Output is correct
12 Correct 7 ms 9052 KB Output is correct
13 Correct 8 ms 9564 KB Output is correct
14 Correct 6 ms 8540 KB Output is correct
15 Correct 5 ms 8144 KB Output is correct
16 Correct 5 ms 8540 KB Output is correct
17 Correct 6 ms 9052 KB Output is correct
18 Correct 5 ms 8536 KB Output is correct
19 Correct 5 ms 9052 KB Output is correct
20 Correct 113 ms 13396 KB Output is correct
21 Correct 94 ms 13396 KB Output is correct
22 Correct 99 ms 13396 KB Output is correct
23 Correct 100 ms 13484 KB Output is correct
24 Correct 340 ms 175824 KB Output is correct
25 Correct 329 ms 175568 KB Output is correct
26 Correct 332 ms 175576 KB Output is correct
27 Correct 344 ms 219604 KB Output is correct
28 Correct 354 ms 219860 KB Output is correct
29 Correct 343 ms 219736 KB Output is correct
30 Correct 340 ms 218980 KB Output is correct
31 Correct 350 ms 214932 KB Output is correct
32 Correct 352 ms 218812 KB Output is correct
33 Correct 254 ms 141260 KB Output is correct
34 Correct 253 ms 122572 KB Output is correct
35 Correct 277 ms 140404 KB Output is correct
36 Correct 335 ms 181208 KB Output is correct
37 Correct 329 ms 170200 KB Output is correct
38 Correct 346 ms 181448 KB Output is correct
39 Correct 479 ms 174416 KB Output is correct
40 Correct 350 ms 174160 KB Output is correct
41 Correct 318 ms 174416 KB Output is correct
42 Correct 362 ms 175440 KB Output is correct
43 Correct 322 ms 174672 KB Output is correct
44 Incorrect 208 ms 14672 KB Output isn't correct
45 Halted 0 ms 0 KB -