oj.uz

Submission #133451

# Submission time Handle Problem Language Result Execution time Memory
133451 2019-07-20T17:37:34 Z duality Bitaro’s Party (JOI18_bitaro) C++11
100 / 100
 1854 ms 241872 KB 
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

vi adjList[100000],C;
vpii best[100000];
int del[100000];
int dp[100000];
int main() {
    int i,j,k;
    int N,M,Q;
    int S,E,T,Y;
    scanf("%d %d %d",&N,&M,&Q);
    for (i = 0; i < M; i++) scanf("%d %d",&S,&E),adjList[E-1].pb(S-1);
    for (i = 0; i < N; i++) {
        best[i].pb(mp(0,i));
        for (j = 0; j < adjList[i].size(); j++) {
            int v = adjList[i][j];
            for (k = 0; k < best[v].size(); k++) best[i].pb(mp(best[v][k].first+1,best[v][k].second));
        }
        int c = 0;
        sort(best[i].begin(),best[i].end(),greater<pii>());
        for (j = 0; j < best[i].size(); j++) {
            if (!del[best[i][j].second]) best[i][c++] = best[i][j],del[best[i][j].second] = 1;
        }
        for (j = 0; j < c; j++) del[best[i][j].second] = 0;
        best[i].resize(min(100,c));
    }
    for (i = 0; i < Q; i++) {
        scanf("%d %d",&T,&Y),T--;
        C.resize(Y);
        for (j = 0; j < Y; j++) scanf("%d",&C[j]),C[j]--,del[C[j]] = 1;
        for (j = 0; j < best[T].size(); j++) {
            if (!del[best[T][j].second]) break;
        }
        if (j < best[T].size()) printf("%d\n",best[T][j].first);
        else {
            for (j = 0; j <= T; j++) {
                dp[j] = del[j] ? -1e9:0;
                for (k = 0; k < adjList[j].size(); k++) dp[j] = max(dp[j],dp[adjList[j][k]]+1);
            }
            printf("%d\n",(dp[T] < 0) ? -1:dp[T]);
        }
        for (j = 0; j < Y; j++) del[C[j]] = 0;
    }

    return 0;
}

Compilation message

bitaro.cpp: In function 'int main()':
bitaro.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < adjList[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:24:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (k = 0; k < best[v].size(); k++) best[i].pb(mp(best[v][k].first+1,best[v][k].second));
                         ~~^~~~~~~~~~~~~~~~
bitaro.cpp:28:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < best[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~
bitaro.cpp:38:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < best[T].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~
bitaro.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (j < best[T].size()) printf("%d\n",best[T][j].first);
             ~~^~~~~~~~~~~~~~~~
bitaro.cpp:45:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (k = 0; k < adjList[j].size(); k++) dp[j] = max(dp[j],dp[adjList[j][k]]+1);
                             ~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&N,&M,&Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:19:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < M; i++) scanf("%d %d",&S,&E),adjList[E-1].pb(S-1);
                             ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:35:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&T,&Y),T--;
         ~~~~~~~~~~~~~~~~~~~~^~~~
bitaro.cpp:37:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for (j = 0; j < Y; j++) scanf("%d",&C[j]),C[j]--,del[C[j]] = 1;
                                 ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 4988 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 11 ms 5752 KB Output is correct
6 Correct 11 ms 5624 KB Output is correct
7 Correct 10 ms 5624 KB Output is correct
8 Correct 15 ms 7032 KB Output is correct
9 Correct 15 ms 7160 KB Output is correct
10 Correct 18 ms 7160 KB Output is correct
11 Correct 18 ms 7032 KB Output is correct
12 Correct 13 ms 6136 KB Output is correct
13 Correct 20 ms 6904 KB Output is correct
14 Correct 15 ms 6264 KB Output is correct
15 Correct 13 ms 6008 KB Output is correct
16 Correct 14 ms 6264 KB Output is correct
17 Correct 15 ms 6392 KB Output is correct
18 Correct 13 ms 6008 KB Output is correct
19 Correct 15 ms 6520 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 4988 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 11 ms 5752 KB Output is correct
6 Correct 11 ms 5624 KB Output is correct
7 Correct 10 ms 5624 KB Output is correct
8 Correct 15 ms 7032 KB Output is correct
9 Correct 15 ms 7160 KB Output is correct
10 Correct 18 ms 7160 KB Output is correct
11 Correct 18 ms 7032 KB Output is correct
12 Correct 13 ms 6136 KB Output is correct
13 Correct 20 ms 6904 KB Output is correct
14 Correct 15 ms 6264 KB Output is correct
15 Correct 13 ms 6008 KB Output is correct
16 Correct 14 ms 6264 KB Output is correct
17 Correct 15 ms 6392 KB Output is correct
18 Correct 13 ms 6008 KB Output is correct
19 Correct 15 ms 6520 KB Output is correct
20 Correct 1784 ms 146328 KB Output is correct
21 Correct 1747 ms 146276 KB Output is correct
22 Correct 1777 ms 145872 KB Output is correct
23 Correct 1768 ms 155412 KB Output is correct
24 Correct 1294 ms 167136 KB Output is correct
25 Correct 1336 ms 176476 KB Output is correct
26 Correct 1303 ms 175840 KB Output is correct
27 Correct 923 ms 240060 KB Output is correct
28 Correct 923 ms 240248 KB Output is correct
29 Correct 913 ms 240624 KB Output is correct
30 Correct 995 ms 239928 KB Output is correct
31 Correct 1152 ms 225300 KB Output is correct
32 Correct 997 ms 239864 KB Output is correct
33 Correct 927 ms 148640 KB Output is correct
34 Correct 895 ms 132312 KB Output is correct
35 Correct 924 ms 147524 KB Output is correct
36 Correct 1171 ms 195264 KB Output is correct
37 Correct 1193 ms 176248 KB Output is correct
38 Correct 1178 ms 196216 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 4988 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 11 ms 5752 KB Output is correct
6 Correct 11 ms 5624 KB Output is correct
7 Correct 10 ms 5624 KB Output is correct
8 Correct 15 ms 7032 KB Output is correct
9 Correct 15 ms 7160 KB Output is correct
10 Correct 18 ms 7160 KB Output is correct
11 Correct 18 ms 7032 KB Output is correct
12 Correct 13 ms 6136 KB Output is correct
13 Correct 20 ms 6904 KB Output is correct
14 Correct 15 ms 6264 KB Output is correct
15 Correct 13 ms 6008 KB Output is correct
16 Correct 14 ms 6264 KB Output is correct
17 Correct 15 ms 6392 KB Output is correct
18 Correct 13 ms 6008 KB Output is correct
19 Correct 15 ms 6520 KB Output is correct
20 Correct 1784 ms 146328 KB Output is correct
21 Correct 1747 ms 146276 KB Output is correct
22 Correct 1777 ms 145872 KB Output is correct
23 Correct 1768 ms 155412 KB Output is correct
24 Correct 1294 ms 167136 KB Output is correct
25 Correct 1336 ms 176476 KB Output is correct
26 Correct 1303 ms 175840 KB Output is correct
27 Correct 923 ms 240060 KB Output is correct
28 Correct 923 ms 240248 KB Output is correct
29 Correct 913 ms 240624 KB Output is correct
30 Correct 995 ms 239928 KB Output is correct
31 Correct 1152 ms 225300 KB Output is correct
32 Correct 997 ms 239864 KB Output is correct
33 Correct 927 ms 148640 KB Output is correct
34 Correct 895 ms 132312 KB Output is correct
35 Correct 924 ms 147524 KB Output is correct
36 Correct 1171 ms 195264 KB Output is correct
37 Correct 1193 ms 176248 KB Output is correct
38 Correct 1178 ms 196216 KB Output is correct
39 Correct 1336 ms 172832 KB Output is correct
40 Correct 1335 ms 175272 KB Output is correct
41 Correct 1320 ms 175480 KB Output is correct
42 Correct 1373 ms 173968 KB Output is correct
43 Correct 1289 ms 172588 KB Output is correct
44 Correct 1829 ms 149108 KB Output is correct
45 Correct 1789 ms 148152 KB Output is correct
46 Correct 1787 ms 148244 KB Output is correct
47 Correct 1780 ms 148076 KB Output is correct
48 Correct 1775 ms 147700 KB Output is correct
49 Correct 977 ms 241528 KB Output is correct
50 Correct 1335 ms 240756 KB Output is correct
51 Correct 1786 ms 148728 KB Output is correct
52 Correct 1808 ms 147920 KB Output is correct
53 Correct 1222 ms 195960 KB Output is correct
54 Correct 1264 ms 177152 KB Output is correct
55 Correct 1185 ms 195856 KB Output is correct
56 Correct 1228 ms 177524 KB Output is correct
57 Correct 1819 ms 148972 KB Output is correct
58 Correct 1828 ms 148848 KB Output is correct
59 Correct 1835 ms 147944 KB Output is correct
60 Correct 1854 ms 147992 KB Output is correct
61 Correct 985 ms 240308 KB Output is correct
62 Correct 1211 ms 196276 KB Output is correct
63 Correct 1236 ms 175480 KB Output is correct
64 Correct 1186 ms 241184 KB Output is correct
65 Correct 1416 ms 195068 KB Output is correct
66 Correct 1222 ms 176716 KB Output is correct
67 Correct 1269 ms 240592 KB Output is correct
68 Correct 1453 ms 196984 KB Output is correct
69 Correct 1185 ms 174232 KB Output is correct
70 Correct 939 ms 240912 KB Output is correct
71 Correct 1170 ms 196344 KB Output is correct
72 Correct 1214 ms 176404 KB Output is correct
73 Correct 948 ms 240632 KB Output is correct
74 Correct 1224 ms 196172 KB Output is correct
75 Correct 1210 ms 176120 KB Output is correct
76 Correct 1002 ms 241872 KB Output is correct
77 Correct 936 ms 240340 KB Output is correct
78 Correct 945 ms 240572 KB Output is correct
79 Correct 1797 ms 149368 KB Output is correct
80 Correct 1779 ms 148064 KB Output is correct
81 Correct 1756 ms 147748 KB Output is correct
82 Correct 1072 ms 240736 KB Output is correct
83 Correct 1236 ms 227516 KB Output is correct
84 Correct 991 ms 240068 KB Output is correct
85 Correct 1195 ms 225408 KB Output is correct
86 Correct 998 ms 240968 KB Output is correct
87 Correct 1166 ms 226908 KB Output is correct
88 Correct 1819 ms 149168 KB Output is correct
89 Correct 1833 ms 148980 KB Output is correct
90 Correct 1789 ms 148340 KB Output is correct
91 Correct 1791 ms 147704 KB Output is correct
92 Correct 1774 ms 148096 KB Output is correct
93 Correct 1785 ms 147416 KB Output is correct
94 Correct 992 ms 149892 KB Output is correct
95 Correct 975 ms 133272 KB Output is correct
96 Correct 935 ms 148068 KB Output is correct
97 Correct 931 ms 134408 KB Output is correct
98 Correct 936 ms 149288 KB Output is correct
99 Correct 919 ms 134000 KB Output is correct
100 Correct 1834 ms 158208 KB Output is correct
101 Correct 1784 ms 157644 KB Output is correct
102 Correct 1785 ms 157040 KB Output is correct
103 Correct 1753 ms 157168 KB Output is correct
104 Correct 1786 ms 157132 KB Output is correct
105 Correct 1774 ms 157092 KB Output is correct
106 Correct 1213 ms 196728 KB Output is correct
107 Correct 1282 ms 178288 KB Output is correct
108 Correct 1177 ms 196672 KB Output is correct
109 Correct 1188 ms 175728 KB Output is correct
110 Correct 1170 ms 197212 KB Output is correct
111 Correct 1212 ms 177620 KB Output is correct
112 Correct 1829 ms 149028 KB Output is correct
113 Correct 1825 ms 149228 KB Output is correct
114 Correct 1776 ms 148400 KB Output is correct
115 Correct 1788 ms 148104 KB Output is correct
116 Correct 1774 ms 147828 KB Output is correct
117 Correct 1819 ms 147956 KB Output is correct
118 Correct 925 ms 240284 KB Output is correct
119 Correct 1163 ms 196472 KB Output is correct
120 Correct 1191 ms 175776 KB Output is correct
121 Correct 920 ms 240288 KB Output is correct
122 Correct 1164 ms 195128 KB Output is correct
123 Correct 1201 ms 174808 KB Output is correct
124 Correct 911 ms 240020 KB Output is correct
125 Correct 1157 ms 196380 KB Output is correct
126 Correct 1210 ms 175592 KB Output is correct