oj.uz

Submission #483294

# Submission time Handle Problem Language Result Execution time Memory
483294 2021-10-28T14:29:28 Z alextodoran Bitaro’s Party (JOI18_bitaro) C++17
100 / 100
 1442 ms 120004 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;

int N, M, Q;

vector <int> out[N_MAX + 2];
vector <int> in[N_MAX + 2];

int K;

vector <pair <int, int>> dp[N_MAX + 2];

bool aux[N_MAX + 2];

int maxLen[N_MAX + 2];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M >> Q;
    for(int i = 1; i <= M; i++)
    {
        int u, v;
        cin >> u >> v;

        out[u].push_back(v);
        in[v].push_back(u);
    }

    K = 100;

    for(int u = 1; u <= N; u++)
    {
        vector <pair <int, int>> vec;
        for(int v : in[u])
        {
            for(pair <int, int> p : dp[v])
                vec.push_back(p);
        }
        sort(vec.begin(), vec.end(), greater <pair <int, int>> ());

        for(pair <int, int> p : vec)
            if(aux[p.second] == false)
            {
                aux[p.second] = true;
                dp[u].push_back(make_pair(p.first + 1, p.second));
                if((int) dp[u].size() == K)
                    break;
            }
        if((int) dp[u].size() < K)
            dp[u].push_back(make_pair(0, u));

        for(pair <int, int> p : dp[u])
            aux[p.second] = false;
    }

    for(int i = 1; i <= Q; i++)
    {
        int u;
        cin >> u;

        int cnt;
        cin >> cnt;
        vector <int> exclude (cnt);
        for(int j = 0; j < cnt; j++)
            cin >> exclude[j];

        for(int v : exclude)
            aux[v] = true;

        if(cnt < K)
        {
            int pos = 0;
            while(pos < (int) dp[u].size() && aux[dp[u][pos].second] == true)
                pos++;
            if(pos == (int) dp[u].size())
                cout << "-1\n";
            else
                cout << dp[u][pos].first << "\n";
        }
        else
        {
            for(int v = 1; v <= N; v++)
            {
                maxLen[v] = (aux[v] == false ? 0 : INT_MIN);
                for(int w : in[v])
                    maxLen[v] = max(maxLen[v], maxLen[w] + 1);
            }
            if(maxLen[u] < 0)
                cout << "-1\n";
            else
                cout << maxLen[u] << "\n";
        }

        for(int v : exclude)
            aux[v] = false;
    }

    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7244 KB Output is correct
2 Correct 3 ms 7244 KB Output is correct
3 Correct 3 ms 7244 KB Output is correct
4 Correct 3 ms 7372 KB Output is correct
5 Correct 7 ms 7756 KB Output is correct
6 Correct 7 ms 7884 KB Output is correct
7 Correct 7 ms 7756 KB Output is correct
8 Correct 9 ms 8396 KB Output is correct
9 Correct 10 ms 8396 KB Output is correct
10 Correct 9 ms 8376 KB Output is correct
11 Correct 10 ms 8392 KB Output is correct
12 Correct 8 ms 8140 KB Output is correct
13 Correct 10 ms 8368 KB Output is correct
14 Correct 10 ms 8012 KB Output is correct
15 Correct 8 ms 7888 KB Output is correct
16 Correct 9 ms 8012 KB Output is correct
17 Correct 9 ms 8144 KB Output is correct
18 Correct 8 ms 8012 KB Output is correct
19 Correct 10 ms 8144 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7244 KB Output is correct
2 Correct 3 ms 7244 KB Output is correct
3 Correct 3 ms 7244 KB Output is correct
4 Correct 3 ms 7372 KB Output is correct
5 Correct 7 ms 7756 KB Output is correct
6 Correct 7 ms 7884 KB Output is correct
7 Correct 7 ms 7756 KB Output is correct
8 Correct 9 ms 8396 KB Output is correct
9 Correct 10 ms 8396 KB Output is correct
10 Correct 9 ms 8376 KB Output is correct
11 Correct 10 ms 8392 KB Output is correct
12 Correct 8 ms 8140 KB Output is correct
13 Correct 10 ms 8368 KB Output is correct
14 Correct 10 ms 8012 KB Output is correct
15 Correct 8 ms 7888 KB Output is correct
16 Correct 9 ms 8012 KB Output is correct
17 Correct 9 ms 8144 KB Output is correct
18 Correct 8 ms 8012 KB Output is correct
19 Correct 10 ms 8144 KB Output is correct
20 Correct 1262 ms 12852 KB Output is correct
21 Correct 1228 ms 12976 KB Output is correct
22 Correct 1266 ms 12916 KB Output is correct
23 Correct 1201 ms 13904 KB Output is correct
24 Correct 739 ms 93248 KB Output is correct
25 Correct 764 ms 94672 KB Output is correct
26 Correct 772 ms 94532 KB Output is correct
27 Correct 604 ms 118884 KB Output is correct
28 Correct 587 ms 118852 KB Output is correct
29 Correct 587 ms 118844 KB Output is correct
30 Correct 678 ms 118104 KB Output is correct
31 Correct 758 ms 116416 KB Output is correct
32 Correct 686 ms 118072 KB Output is correct
33 Correct 557 ms 80616 KB Output is correct
34 Correct 539 ms 73428 KB Output is correct
35 Correct 547 ms 80476 KB Output is correct
36 Correct 629 ms 99400 KB Output is correct
37 Correct 665 ms 94876 KB Output is correct
38 Correct 633 ms 99568 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7244 KB Output is correct
2 Correct 3 ms 7244 KB Output is correct
3 Correct 3 ms 7244 KB Output is correct
4 Correct 3 ms 7372 KB Output is correct
5 Correct 7 ms 7756 KB Output is correct
6 Correct 7 ms 7884 KB Output is correct
7 Correct 7 ms 7756 KB Output is correct
8 Correct 9 ms 8396 KB Output is correct
9 Correct 10 ms 8396 KB Output is correct
10 Correct 9 ms 8376 KB Output is correct
11 Correct 10 ms 8392 KB Output is correct
12 Correct 8 ms 8140 KB Output is correct
13 Correct 10 ms 8368 KB Output is correct
14 Correct 10 ms 8012 KB Output is correct
15 Correct 8 ms 7888 KB Output is correct
16 Correct 9 ms 8012 KB Output is correct
17 Correct 9 ms 8144 KB Output is correct
18 Correct 8 ms 8012 KB Output is correct
19 Correct 10 ms 8144 KB Output is correct
20 Correct 1262 ms 12852 KB Output is correct
21 Correct 1228 ms 12976 KB Output is correct
22 Correct 1266 ms 12916 KB Output is correct
23 Correct 1201 ms 13904 KB Output is correct
24 Correct 739 ms 93248 KB Output is correct
25 Correct 764 ms 94672 KB Output is correct
26 Correct 772 ms 94532 KB Output is correct
27 Correct 604 ms 118884 KB Output is correct
28 Correct 587 ms 118852 KB Output is correct
29 Correct 587 ms 118844 KB Output is correct
30 Correct 678 ms 118104 KB Output is correct
31 Correct 758 ms 116416 KB Output is correct
32 Correct 686 ms 118072 KB Output is correct
33 Correct 557 ms 80616 KB Output is correct
34 Correct 539 ms 73428 KB Output is correct
35 Correct 547 ms 80476 KB Output is correct
36 Correct 629 ms 99400 KB Output is correct
37 Correct 665 ms 94876 KB Output is correct
38 Correct 633 ms 99568 KB Output is correct
39 Correct 807 ms 94284 KB Output is correct
40 Correct 762 ms 94300 KB Output is correct
41 Correct 1433 ms 94620 KB Output is correct
42 Correct 906 ms 94336 KB Output is correct
43 Correct 768 ms 93892 KB Output is correct
44 Correct 1275 ms 13812 KB Output is correct
45 Correct 1255 ms 12952 KB Output is correct
46 Correct 1387 ms 12868 KB Output is correct
47 Correct 1267 ms 12824 KB Output is correct
48 Correct 1242 ms 12732 KB Output is correct
49 Correct 635 ms 119448 KB Output is correct
50 Correct 1247 ms 118724 KB Output is correct
51 Correct 1241 ms 13752 KB Output is correct
52 Correct 1354 ms 12972 KB Output is correct
53 Correct 663 ms 99780 KB Output is correct
54 Correct 687 ms 95596 KB Output is correct
55 Correct 1355 ms 99092 KB Output is correct
56 Correct 1440 ms 95324 KB Output is correct
57 Correct 1302 ms 13648 KB Output is correct
58 Correct 1264 ms 13460 KB Output is correct
59 Correct 1370 ms 12912 KB Output is correct
60 Correct 1368 ms 13556 KB Output is correct
61 Correct 733 ms 118820 KB Output is correct
62 Correct 784 ms 99632 KB Output is correct
63 Correct 796 ms 94696 KB Output is correct
64 Correct 999 ms 118744 KB Output is correct
65 Correct 1063 ms 99272 KB Output is correct
66 Correct 1108 ms 95300 KB Output is correct
67 Correct 1228 ms 118800 KB Output is correct
68 Correct 1346 ms 99548 KB Output is correct
69 Correct 1383 ms 94208 KB Output is correct
70 Correct 594 ms 118812 KB Output is correct
71 Correct 653 ms 99480 KB Output is correct
72 Correct 693 ms 94788 KB Output is correct
73 Correct 651 ms 119064 KB Output is correct
74 Correct 677 ms 99624 KB Output is correct
75 Correct 697 ms 94840 KB Output is correct
76 Correct 640 ms 120004 KB Output is correct
77 Correct 1321 ms 119072 KB Output is correct
78 Correct 633 ms 119096 KB Output is correct
79 Correct 1302 ms 13804 KB Output is correct
80 Correct 1350 ms 13108 KB Output is correct
81 Correct 1238 ms 12936 KB Output is correct
82 Correct 717 ms 119176 KB Output is correct
83 Correct 796 ms 117316 KB Output is correct
84 Correct 1361 ms 118236 KB Output is correct
85 Correct 1442 ms 116452 KB Output is correct
86 Correct 684 ms 118340 KB Output is correct
87 Correct 778 ms 116456 KB Output is correct
88 Correct 1290 ms 13636 KB Output is correct
89 Correct 1278 ms 13660 KB Output is correct
90 Correct 1367 ms 12868 KB Output is correct
91 Correct 1385 ms 12864 KB Output is correct
92 Correct 1257 ms 12796 KB Output is correct
93 Correct 1253 ms 12956 KB Output is correct
94 Correct 588 ms 81516 KB Output is correct
95 Correct 581 ms 74064 KB Output is correct
96 Correct 1219 ms 80380 KB Output is correct
97 Correct 1292 ms 74304 KB Output is correct
98 Correct 585 ms 80880 KB Output is correct
99 Correct 554 ms 74060 KB Output is correct
100 Correct 1270 ms 13676 KB Output is correct
101 Correct 1241 ms 14052 KB Output is correct
102 Correct 1358 ms 13564 KB Output is correct
103 Correct 1336 ms 13992 KB Output is correct
104 Correct 1234 ms 13352 KB Output is correct
105 Correct 1195 ms 13904 KB Output is correct
106 Correct 671 ms 100164 KB Output is correct
107 Correct 707 ms 95836 KB Output is correct
108 Correct 1377 ms 99780 KB Output is correct
109 Correct 1386 ms 95072 KB Output is correct
110 Correct 658 ms 100028 KB Output is correct
111 Correct 683 ms 95380 KB Output is correct
112 Correct 1264 ms 13788 KB Output is correct
113 Correct 1273 ms 13896 KB Output is correct
114 Correct 1373 ms 13112 KB Output is correct
115 Correct 1394 ms 13392 KB Output is correct
116 Correct 1252 ms 12688 KB Output is correct
117 Correct 1256 ms 13264 KB Output is correct
118 Correct 594 ms 118264 KB Output is correct
119 Correct 655 ms 99060 KB Output is correct
120 Correct 668 ms 94564 KB Output is correct
121 Correct 594 ms 118340 KB Output is correct
122 Correct 649 ms 98928 KB Output is correct
123 Correct 662 ms 94664 KB Output is correct
124 Correct 601 ms 118220 KB Output is correct
125 Correct 648 ms 99240 KB Output is correct
126 Correct 659 ms 94636 KB Output is correct