oj.uz

Submission #778543

# Submission time Handle Problem Language Result Execution time Memory
778543 2023-07-10T12:00:48 Z borisAngelov Bitaro’s Party (JOI18_bitaro) C++17
100 / 100
 963 ms 249144 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const int SQRT = 300;

int n, m, q;

vector<int> g[maxn];

bool bad[maxn];
int dp[maxn];

bool visited[maxn];

int c[maxn];

int calc(int node)
{
    memset(dp, -1, sizeof(dp));
    dp[node] = 0;

    for (int i = node - 1; i >= 1; --i)
    {
        for (auto prv : g[i])
        {
            if (dp[prv] != -1)
            {
                dp[i] = max(dp[i], 1 + dp[prv]);
            }
        }
    }

    int ans = -1;

    for (int i = node; i >= 1; --i)
    {
        if (bad[i] == false)
        {
            ans = max(ans, dp[i]);
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        bad[i] = false;
    }

    return ans;
}

pair<int, int> max_dist[maxn][SQRT + 5];

void precompute_small()
{
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j < SQRT; ++j)
        {
            max_dist[i][j].first = -1;
        }

        max_dist[i][0].first = 0;
        max_dist[i][0].second = i;
    }

    for (int i = 1; i <= n; ++i)
    {
        for (auto to : g[i])
        {
            int ptr1 = 0;
            int ptr2 = 0;

            vector<pair<int, int>> combined;

            int iter = 0;

            while (true)
            {
                if (combined.size() >= SQRT)
                {
                    break;
                }

                pair<int, int> curr = make_pair(0, 0);

                if (max_dist[i][ptr1].first != -1 && max_dist[i][ptr1].first + 1 > max_dist[to][ptr2].first)
                {
                    curr = make_pair(max_dist[i][ptr1].first + 1, max_dist[i][ptr1].second);
                    ++ptr1;
                }
                else if (max_dist[to][ptr2].first != -1)
                {
                    curr = make_pair(max_dist[to][ptr2].first, max_dist[to][ptr2].second);
                    ++ptr2;
                }
                else
                {
                    break;
                }

                if (visited[curr.second] == false)
                {
                    visited[curr.second] = true;
                    combined.push_back(curr);
                }
            }

            for (int j = 0; j < combined.size(); ++j)
            {
                max_dist[to][j] = combined[j];
            }

            for (int j = 0; j < combined.size(); ++j)
            {
                visited[combined[j].second] = false;
            }
        }
    }
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> m >> q;

    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        cin >> x >> y;

        g[x].push_back(y);
    }

    precompute_small();

    for (int i = 1; i <= q; ++i)
    {
        int node, cnt;
        cin >> node >> cnt;

        for (int j = 1; j <= cnt; ++j)
        {
            cin >> c[j];
            bad[c[j]] = true;
        }

        if (cnt >= SQRT)
        {
            int ans = calc(node);
            cout << ans << "\n";
        }
        else
        {
            bool flag = true;

            for (int j = 0; j <= SQRT; ++j)
            {
                if (max_dist[node][j].first < 0)
                {
                    flag = false;
                    break;
                }

                if (bad[max_dist[node][j].second] == false)
                {
                    cout << max_dist[node][j].first << "\n";
                    break;
                }
            }

            if (flag == false)
            {
                cout << -1 << "\n";
            }

            for (int j = 1; j <= cnt; ++j)
            {
                bad[c[j]] = false;
            }
        }
    }

    return 0;
}

Compilation message

bitaro.cpp: In function 'void precompute_small()':
bitaro.cpp:110:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |             for (int j = 0; j < combined.size(); ++j)
      |                             ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:115:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |             for (int j = 0; j < combined.size(); ++j)
      |                             ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:77:17: warning: unused variable 'iter' [-Wunused-variable]
   77 |             int iter = 0;
      |                 ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 3 ms 5460 KB Output is correct
6 Correct 5 ms 5508 KB Output is correct
7 Correct 4 ms 5504 KB Output is correct
8 Correct 7 ms 5460 KB Output is correct
9 Correct 7 ms 5460 KB Output is correct
10 Correct 7 ms 5532 KB Output is correct
11 Correct 7 ms 5512 KB Output is correct
12 Correct 5 ms 5460 KB Output is correct
13 Correct 6 ms 5460 KB Output is correct
14 Correct 6 ms 5460 KB Output is correct
15 Correct 5 ms 5460 KB Output is correct
16 Correct 6 ms 5504 KB Output is correct
17 Correct 6 ms 5520 KB Output is correct
18 Correct 5 ms 5512 KB Output is correct
19 Correct 6 ms 5524 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 3 ms 5460 KB Output is correct
6 Correct 5 ms 5508 KB Output is correct
7 Correct 4 ms 5504 KB Output is correct
8 Correct 7 ms 5460 KB Output is correct
9 Correct 7 ms 5460 KB Output is correct
10 Correct 7 ms 5532 KB Output is correct
11 Correct 7 ms 5512 KB Output is correct
12 Correct 5 ms 5460 KB Output is correct
13 Correct 6 ms 5460 KB Output is correct
14 Correct 6 ms 5460 KB Output is correct
15 Correct 5 ms 5460 KB Output is correct
16 Correct 6 ms 5504 KB Output is correct
17 Correct 6 ms 5520 KB Output is correct
18 Correct 5 ms 5512 KB Output is correct
19 Correct 6 ms 5524 KB Output is correct
20 Correct 418 ms 8192 KB Output is correct
21 Correct 413 ms 8236 KB Output is correct
22 Correct 415 ms 8204 KB Output is correct
23 Correct 518 ms 8260 KB Output is correct
24 Correct 566 ms 246988 KB Output is correct
25 Correct 603 ms 247092 KB Output is correct
26 Correct 595 ms 247080 KB Output is correct
27 Correct 742 ms 248112 KB Output is correct
28 Correct 730 ms 248108 KB Output is correct
29 Correct 727 ms 248108 KB Output is correct
30 Correct 757 ms 247440 KB Output is correct
31 Correct 703 ms 247412 KB Output is correct
32 Correct 749 ms 247448 KB Output is correct
33 Correct 572 ms 247920 KB Output is correct
34 Correct 510 ms 247964 KB Output is correct
35 Correct 575 ms 248012 KB Output is correct
36 Correct 677 ms 248116 KB Output is correct
37 Correct 621 ms 248112 KB Output is correct
38 Correct 672 ms 248060 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 3 ms 5460 KB Output is correct
6 Correct 5 ms 5508 KB Output is correct
7 Correct 4 ms 5504 KB Output is correct
8 Correct 7 ms 5460 KB Output is correct
9 Correct 7 ms 5460 KB Output is correct
10 Correct 7 ms 5532 KB Output is correct
11 Correct 7 ms 5512 KB Output is correct
12 Correct 5 ms 5460 KB Output is correct
13 Correct 6 ms 5460 KB Output is correct
14 Correct 6 ms 5460 KB Output is correct
15 Correct 5 ms 5460 KB Output is correct
16 Correct 6 ms 5504 KB Output is correct
17 Correct 6 ms 5520 KB Output is correct
18 Correct 5 ms 5512 KB Output is correct
19 Correct 6 ms 5524 KB Output is correct
20 Correct 418 ms 8192 KB Output is correct
21 Correct 413 ms 8236 KB Output is correct
22 Correct 415 ms 8204 KB Output is correct
23 Correct 518 ms 8260 KB Output is correct
24 Correct 566 ms 246988 KB Output is correct
25 Correct 603 ms 247092 KB Output is correct
26 Correct 595 ms 247080 KB Output is correct
27 Correct 742 ms 248112 KB Output is correct
28 Correct 730 ms 248108 KB Output is correct
29 Correct 727 ms 248108 KB Output is correct
30 Correct 757 ms 247440 KB Output is correct
31 Correct 703 ms 247412 KB Output is correct
32 Correct 749 ms 247448 KB Output is correct
33 Correct 572 ms 247920 KB Output is correct
34 Correct 510 ms 247964 KB Output is correct
35 Correct 575 ms 248012 KB Output is correct
36 Correct 677 ms 248116 KB Output is correct
37 Correct 621 ms 248112 KB Output is correct
38 Correct 672 ms 248060 KB Output is correct
39 Correct 605 ms 247848 KB Output is correct
40 Correct 598 ms 246884 KB Output is correct
41 Correct 600 ms 246828 KB Output is correct
42 Correct 649 ms 247244 KB Output is correct
43 Correct 603 ms 247216 KB Output is correct
44 Correct 445 ms 9116 KB Output is correct
45 Correct 425 ms 8216 KB Output is correct
46 Correct 424 ms 8100 KB Output is correct
47 Correct 472 ms 8532 KB Output is correct
48 Correct 421 ms 8140 KB Output is correct
49 Correct 778 ms 248756 KB Output is correct
50 Correct 730 ms 247472 KB Output is correct
51 Correct 429 ms 9004 KB Output is correct
52 Correct 434 ms 8100 KB Output is correct
53 Correct 727 ms 248656 KB Output is correct
54 Correct 699 ms 248368 KB Output is correct
55 Correct 687 ms 247476 KB Output is correct
56 Correct 648 ms 247500 KB Output is correct
57 Correct 436 ms 8996 KB Output is correct
58 Correct 448 ms 8984 KB Output is correct
59 Correct 426 ms 8140 KB Output is correct
60 Correct 427 ms 8184 KB Output is correct
61 Correct 815 ms 248144 KB Output is correct
62 Correct 750 ms 247984 KB Output is correct
63 Correct 681 ms 248112 KB Output is correct
64 Correct 963 ms 248172 KB Output is correct
65 Correct 881 ms 247980 KB Output is correct
66 Correct 800 ms 248140 KB Output is correct
67 Correct 723 ms 247500 KB Output is correct
68 Correct 685 ms 247548 KB Output is correct
69 Correct 629 ms 247500 KB Output is correct
70 Correct 745 ms 248196 KB Output is correct
71 Correct 688 ms 248196 KB Output is correct
72 Correct 627 ms 248140 KB Output is correct
73 Correct 785 ms 248116 KB Output is correct
74 Correct 704 ms 248116 KB Output is correct
75 Correct 680 ms 248120 KB Output is correct
76 Correct 773 ms 249144 KB Output is correct
77 Correct 740 ms 247856 KB Output is correct
78 Correct 751 ms 248360 KB Output is correct
79 Correct 435 ms 9164 KB Output is correct
80 Correct 420 ms 8252 KB Output is correct
81 Correct 422 ms 8140 KB Output is correct
82 Correct 812 ms 248540 KB Output is correct
83 Correct 747 ms 248304 KB Output is correct
84 Correct 747 ms 247184 KB Output is correct
85 Correct 719 ms 247160 KB Output is correct
86 Correct 768 ms 247632 KB Output is correct
87 Correct 727 ms 247540 KB Output is correct
88 Correct 451 ms 9208 KB Output is correct
89 Correct 439 ms 9112 KB Output is correct
90 Correct 428 ms 8340 KB Output is correct
91 Correct 427 ms 8240 KB Output is correct
92 Correct 426 ms 8344 KB Output is correct
93 Correct 420 ms 8140 KB Output is correct
94 Correct 633 ms 248816 KB Output is correct
95 Correct 553 ms 248784 KB Output is correct
96 Correct 582 ms 247744 KB Output is correct
97 Correct 519 ms 247716 KB Output is correct
98 Correct 608 ms 248180 KB Output is correct
99 Correct 528 ms 248180 KB Output is correct
100 Correct 542 ms 9120 KB Output is correct
101 Correct 556 ms 9188 KB Output is correct
102 Correct 533 ms 8220 KB Output is correct
103 Correct 527 ms 8140 KB Output is correct
104 Correct 531 ms 8272 KB Output is correct
105 Correct 531 ms 8284 KB Output is correct
106 Correct 722 ms 249012 KB Output is correct
107 Correct 647 ms 248880 KB Output is correct
108 Correct 684 ms 247884 KB Output is correct
109 Correct 634 ms 247860 KB Output is correct
110 Correct 691 ms 248268 KB Output is correct
111 Correct 631 ms 248240 KB Output is correct
112 Correct 436 ms 9116 KB Output is correct
113 Correct 454 ms 9248 KB Output is correct
114 Correct 443 ms 8208 KB Output is correct
115 Correct 434 ms 8264 KB Output is correct
116 Correct 432 ms 8140 KB Output is correct
117 Correct 434 ms 8292 KB Output is correct
118 Correct 780 ms 247424 KB Output is correct
119 Correct 685 ms 247480 KB Output is correct
120 Correct 644 ms 247468 KB Output is correct
121 Correct 761 ms 247476 KB Output is correct
122 Correct 693 ms 247476 KB Output is correct
123 Correct 660 ms 247480 KB Output is correct
124 Correct 781 ms 247520 KB Output is correct
125 Correct 732 ms 247472 KB Output is correct
126 Correct 749 ms 247472 KB Output is correct