oj.uz

Submission #1081772

# Submission time Handle Problem Language Result Execution time Memory
1081772 2024-08-30T10:20:54 Z KALARRY Bitaro’s Party (JOI18_bitaro) C++14
100 / 100
 1808 ms 219756 KB 
//chockolateman

#include<bits/stdc++.h>

using namespace std;

int S = 150;

int N,M,Q,cur_dp[100005];
vector<pair<int,int>> dp[100005];
vector<int> adj_rev[100005];
bool visited[100005],prohibited[100005];
vector<pair<int,int>> temp;
bool did[100005];

void dfs(int v)
{
    if(visited[v])
        return;
    visited[v] = true;
    temp.push_back({-1,0});
    temp.push_back({0,v});
    for(auto u : adj_rev[v])
    {
        dfs(u);
        for(auto x : dp[u])
            if(x.first != -1)
                temp.push_back({x.first+1,x.second});
    }
    sort(temp.begin(),temp.end(),greater<pair<int,int>>());
    for(auto x : temp)
    {
        if(dp[v].size()==S)
            break;
        if(!did[x.second])
        {
            did[x.second] = true;
            dp[v].push_back(x);
        }
    }
    for(auto x : dp[v])
        did[x.second] = false;
    temp.clear();
    
}

void dfs2(int v)
{
    if(visited[v])
        return;
    visited[v] = true;
    if(!prohibited[v])
        cur_dp[v] = 0;
    for(auto u : adj_rev[v])
    {
        dfs2(u);
        if(cur_dp[u] != -1)
            cur_dp[v] = max(cur_dp[v],cur_dp[u] + 1);
    }
}

int main()
{
    scanf("%d%d%d",&N,&M,&Q);
    for(int a,b,i = 1 ; i <= M ; i++)
    {
        scanf("%d%d",&a,&b);
        adj_rev[b].push_back(a);
    }
    for(int i = 1 ; i <= N ; i++)
        dfs(i);
    for(int t,y,i = 1 ; i <= Q ; i++)
    {
        vector<int> busy;
        scanf("%d%d",&t,&y);
        for(int a,j = 1 ; j <= y ; j++)
        {
            scanf("%d",&a);
            busy.push_back(a);
            prohibited[a] = true;
        }
        if(busy.size() <= S)
        {
            int ans = -1;
            for(auto x : dp[t])
                if(!prohibited[x.second])
                    ans = max(ans,x.first);
            printf("%d\n",ans);
        }
        else
        {
            for(int j = 1 ; j <= N ; j++)
            {
                cur_dp[j] = -1;
                visited[j] = false;
            }
            dfs2(t);
            printf("%d\n",cur_dp[t]);
        }
        for(auto a : busy)
            prohibited[a] = false;
    }
    return 0;
}

Compilation message

bitaro.cpp: In function 'void dfs(int)':
bitaro.cpp:33:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |         if(dp[v].size()==S)
      |            ~~~~~~~~~~~~^~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:82:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |         if(busy.size() <= S)
      |            ~~~~~~~~~~~~^~~~
bitaro.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf("%d%d%d",&N,&M,&Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d%d",&t,&y);
      |         ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |             scanf("%d",&a);
      |             ~~~~~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 6 ms 5468 KB Output is correct
6 Correct 6 ms 5464 KB Output is correct
7 Correct 5 ms 5464 KB Output is correct
8 Correct 13 ms 7004 KB Output is correct
9 Correct 13 ms 7056 KB Output is correct
10 Correct 12 ms 7004 KB Output is correct
11 Correct 15 ms 6768 KB Output is correct
12 Correct 11 ms 6232 KB Output is correct
13 Correct 17 ms 6748 KB Output is correct
14 Correct 12 ms 6236 KB Output is correct
15 Correct 7 ms 5724 KB Output is correct
16 Correct 12 ms 6236 KB Output is correct
17 Correct 11 ms 6480 KB Output is correct
18 Correct 8 ms 5976 KB Output is correct
19 Correct 13 ms 6488 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 6 ms 5468 KB Output is correct
6 Correct 6 ms 5464 KB Output is correct
7 Correct 5 ms 5464 KB Output is correct
8 Correct 13 ms 7004 KB Output is correct
9 Correct 13 ms 7056 KB Output is correct
10 Correct 12 ms 7004 KB Output is correct
11 Correct 15 ms 6768 KB Output is correct
12 Correct 11 ms 6232 KB Output is correct
13 Correct 17 ms 6748 KB Output is correct
14 Correct 12 ms 6236 KB Output is correct
15 Correct 7 ms 5724 KB Output is correct
16 Correct 12 ms 6236 KB Output is correct
17 Correct 11 ms 6480 KB Output is correct
18 Correct 8 ms 5976 KB Output is correct
19 Correct 13 ms 6488 KB Output is correct
20 Correct 1564 ms 8484 KB Output is correct
21 Correct 1531 ms 9952 KB Output is correct
22 Correct 1588 ms 9844 KB Output is correct
23 Correct 1526 ms 10752 KB Output is correct
24 Correct 1103 ms 153812 KB Output is correct
25 Correct 1193 ms 158316 KB Output is correct
26 Correct 1223 ms 158396 KB Output is correct
27 Correct 1174 ms 217040 KB Output is correct
28 Correct 1099 ms 217296 KB Output is correct
29 Correct 1111 ms 218512 KB Output is correct
30 Correct 1247 ms 213420 KB Output is correct
31 Correct 1421 ms 208176 KB Output is correct
32 Correct 1243 ms 213564 KB Output is correct
33 Correct 952 ms 135896 KB Output is correct
34 Correct 937 ms 117924 KB Output is correct
35 Correct 1010 ms 134860 KB Output is correct
36 Correct 1196 ms 174772 KB Output is correct
37 Correct 1268 ms 163228 KB Output is correct
38 Correct 1226 ms 175056 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 6 ms 5468 KB Output is correct
6 Correct 6 ms 5464 KB Output is correct
7 Correct 5 ms 5464 KB Output is correct
8 Correct 13 ms 7004 KB Output is correct
9 Correct 13 ms 7056 KB Output is correct
10 Correct 12 ms 7004 KB Output is correct
11 Correct 15 ms 6768 KB Output is correct
12 Correct 11 ms 6232 KB Output is correct
13 Correct 17 ms 6748 KB Output is correct
14 Correct 12 ms 6236 KB Output is correct
15 Correct 7 ms 5724 KB Output is correct
16 Correct 12 ms 6236 KB Output is correct
17 Correct 11 ms 6480 KB Output is correct
18 Correct 8 ms 5976 KB Output is correct
19 Correct 13 ms 6488 KB Output is correct
20 Correct 1564 ms 8484 KB Output is correct
21 Correct 1531 ms 9952 KB Output is correct
22 Correct 1588 ms 9844 KB Output is correct
23 Correct 1526 ms 10752 KB Output is correct
24 Correct 1103 ms 153812 KB Output is correct
25 Correct 1193 ms 158316 KB Output is correct
26 Correct 1223 ms 158396 KB Output is correct
27 Correct 1174 ms 217040 KB Output is correct
28 Correct 1099 ms 217296 KB Output is correct
29 Correct 1111 ms 218512 KB Output is correct
30 Correct 1247 ms 213420 KB Output is correct
31 Correct 1421 ms 208176 KB Output is correct
32 Correct 1243 ms 213564 KB Output is correct
33 Correct 952 ms 135896 KB Output is correct
34 Correct 937 ms 117924 KB Output is correct
35 Correct 1010 ms 134860 KB Output is correct
36 Correct 1196 ms 174772 KB Output is correct
37 Correct 1268 ms 163228 KB Output is correct
38 Correct 1226 ms 175056 KB Output is correct
39 Correct 1160 ms 155620 KB Output is correct
40 Correct 1146 ms 156028 KB Output is correct
41 Correct 1200 ms 156240 KB Output is correct
42 Correct 1166 ms 156756 KB Output is correct
43 Correct 1141 ms 156020 KB Output is correct
44 Correct 1602 ms 11336 KB Output is correct
45 Correct 1618 ms 10476 KB Output is correct
46 Correct 1643 ms 10284 KB Output is correct
47 Correct 1591 ms 10060 KB Output is correct
48 Correct 1575 ms 10000 KB Output is correct
49 Correct 1174 ms 213972 KB Output is correct
50 Correct 1074 ms 212820 KB Output is correct
51 Correct 1613 ms 11212 KB Output is correct
52 Correct 1559 ms 10280 KB Output is correct
53 Correct 1237 ms 174420 KB Output is correct
54 Correct 1365 ms 163272 KB Output is correct
55 Correct 1214 ms 173400 KB Output is correct
56 Correct 1261 ms 163096 KB Output is correct
57 Correct 1622 ms 11084 KB Output is correct
58 Correct 1593 ms 11460 KB Output is correct
59 Correct 1604 ms 10248 KB Output is correct
60 Correct 1577 ms 10624 KB Output is correct
61 Correct 1290 ms 219312 KB Output is correct
62 Correct 1326 ms 174672 KB Output is correct
63 Correct 1280 ms 162260 KB Output is correct
64 Correct 1504 ms 219392 KB Output is correct
65 Correct 1536 ms 173948 KB Output is correct
66 Correct 1438 ms 163416 KB Output is correct
67 Correct 1808 ms 219380 KB Output is correct
68 Correct 1718 ms 174664 KB Output is correct
69 Correct 1540 ms 161404 KB Output is correct
70 Correct 1170 ms 218964 KB Output is correct
71 Correct 1238 ms 174672 KB Output is correct
72 Correct 1246 ms 162976 KB Output is correct
73 Correct 1219 ms 219360 KB Output is correct
74 Correct 1266 ms 174596 KB Output is correct
75 Correct 1314 ms 162832 KB Output is correct
76 Correct 1390 ms 214464 KB Output is correct
77 Correct 1621 ms 219756 KB Output is correct
78 Correct 1205 ms 219428 KB Output is correct
79 Correct 1704 ms 11124 KB Output is correct
80 Correct 1660 ms 10208 KB Output is correct
81 Correct 1669 ms 10008 KB Output is correct
82 Correct 1583 ms 214168 KB Output is correct
83 Correct 1529 ms 208976 KB Output is correct
84 Correct 1532 ms 214532 KB Output is correct
85 Correct 1642 ms 207956 KB Output is correct
86 Correct 1253 ms 214484 KB Output is correct
87 Correct 1500 ms 208644 KB Output is correct
88 Correct 1637 ms 11144 KB Output is correct
89 Correct 1601 ms 11312 KB Output is correct
90 Correct 1607 ms 10320 KB Output is correct
91 Correct 1641 ms 10168 KB Output is correct
92 Correct 1592 ms 9924 KB Output is correct
93 Correct 1567 ms 9876 KB Output is correct
94 Correct 1008 ms 136756 KB Output is correct
95 Correct 939 ms 118284 KB Output is correct
96 Correct 1185 ms 135160 KB Output is correct
97 Correct 1082 ms 119512 KB Output is correct
98 Correct 955 ms 135948 KB Output is correct
99 Correct 942 ms 119152 KB Output is correct
100 Correct 1605 ms 11464 KB Output is correct
101 Correct 1551 ms 11624 KB Output is correct
102 Correct 1609 ms 10696 KB Output is correct
103 Correct 1611 ms 10696 KB Output is correct
104 Correct 1582 ms 10572 KB Output is correct
105 Correct 1553 ms 10440 KB Output is correct
106 Correct 1329 ms 175080 KB Output is correct
107 Correct 1344 ms 164080 KB Output is correct
108 Correct 1423 ms 175188 KB Output is correct
109 Correct 1310 ms 162892 KB Output is correct
110 Correct 1259 ms 175584 KB Output is correct
111 Correct 1238 ms 163668 KB Output is correct
112 Correct 1609 ms 11348 KB Output is correct
113 Correct 1628 ms 11520 KB Output is correct
114 Correct 1576 ms 10316 KB Output is correct
115 Correct 1659 ms 10676 KB Output is correct
116 Correct 1571 ms 10016 KB Output is correct
117 Correct 1581 ms 10596 KB Output is correct
118 Correct 1171 ms 212816 KB Output is correct
119 Correct 1199 ms 174312 KB Output is correct
120 Correct 1286 ms 162248 KB Output is correct
121 Correct 1103 ms 212796 KB Output is correct
122 Correct 1249 ms 173648 KB Output is correct
123 Correct 1222 ms 162060 KB Output is correct
124 Correct 1131 ms 212832 KB Output is correct
125 Correct 1229 ms 174748 KB Output is correct
126 Correct 1272 ms 161580 KB Output is correct