# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
166282 | 2019-12-01T12:40:22 Z | georgerapeanu | Bitaro’s Party (JOI18_bitaro) | C++11 | 1718 ms | 264296 KB |
#include <cstdio> #include <vector> #include <algorithm> using namespace std; const int NMAX = 1e5; const int MMAX = 2e5; const int QMAX = 1e5; const int BUCK = 320; int n,m; int q; vector<int> graph[NMAX + 5]; vector<pair<int,int> > cache[NMAX + 5]; bool banned[NMAX + 5]; vector<int> list; int dp[NMAX + 5]; vector<pair<int,int> > tmp; const int LEN = 1 << 14; char buff[LEN]; int ind = LEN - 1; int i32() { int ans = 0; while(buff[ind] < '0' || buff[ind] > '9') { if(++ind >= LEN) { ind = 0; fread(buff,1,LEN,stdin); } } while(!(buff[ind] < '0' || buff[ind] > '9')) { ans = ans * 10 + (buff[ind] - '0'); if(++ind >= LEN) { ind = 0; fread(buff,1,LEN,stdin); } } return ans; } bool used[NMAX + 5]; void merge_to(const vector<pair<int,int> > &s,vector<pair<int,int> > &t) { vector<pair<int,int> > tmp; int x = 0; int y = 0; while((int)tmp.size() < BUCK && (x < (int)s.size() || y < (int)t.size())) { if(x < (int)s.size() && (y == (int)t.size() || s[x].first + 1 >= t[y].first)) { if(used[s[x].second] == false){ tmp.push_back({s[x].first + 1,s[x].second}); used[s[x].second] = true; } x++; } else { if(used[t[y].second] == false){ tmp.push_back(t[y]); used[t[y].second] = true; } y++; } } t = tmp; for(auto it:t){ used[it.second] = false; } } int main() { n = i32(); m = i32(); q = i32(); for(int i = 1; i <= m; i++) { int x,y; x = i32(); y = i32(); graph[y].push_back(x); } for(int i = 1; i <= n; i++) { cache[i].push_back({0,i}); for(auto it:graph[i]) { merge_to(cache[it],cache[i]); } } while(q--) { int town,sz; town = i32(); sz = i32(); for(int i = 1; i <= sz; i++) { int val; val = i32(); list.push_back(val); banned[val] = true; } bool ok = false; for(auto it:cache[town]) { if(banned[it.second]) { continue; } printf("%d\n",it.first); ok = true; break; } if(ok == false) { for(int i = 1; i <= town; i++) { dp[i] = (banned[i] ? -1e9:0); for(auto it:graph[i]) { dp[i] = max(dp[i],dp[it] + 1); } } printf("%d\n",(dp[town] < 0 ? -1:dp[town])); } for(auto it:list) { banned[it] = false; } list.clear(); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4988 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Correct | 6 ms | 4984 KB | Output is correct |
4 | Correct | 6 ms | 4984 KB | Output is correct |
5 | Correct | 10 ms | 5360 KB | Output is correct |
6 | Correct | 10 ms | 5368 KB | Output is correct |
7 | Correct | 9 ms | 5368 KB | Output is correct |
8 | Correct | 19 ms | 7280 KB | Output is correct |
9 | Correct | 19 ms | 7160 KB | Output is correct |
10 | Correct | 19 ms | 7160 KB | Output is correct |
11 | Correct | 18 ms | 7032 KB | Output is correct |
12 | Correct | 13 ms | 6008 KB | Output is correct |
13 | Correct | 18 ms | 6904 KB | Output is correct |
14 | Correct | 17 ms | 6392 KB | Output is correct |
15 | Correct | 12 ms | 5624 KB | Output is correct |
16 | Correct | 16 ms | 6264 KB | Output is correct |
17 | Correct | 16 ms | 6520 KB | Output is correct |
18 | Correct | 13 ms | 5880 KB | Output is correct |
19 | Correct | 16 ms | 6520 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4988 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Correct | 6 ms | 4984 KB | Output is correct |
4 | Correct | 6 ms | 4984 KB | Output is correct |
5 | Correct | 10 ms | 5360 KB | Output is correct |
6 | Correct | 10 ms | 5368 KB | Output is correct |
7 | Correct | 9 ms | 5368 KB | Output is correct |
8 | Correct | 19 ms | 7280 KB | Output is correct |
9 | Correct | 19 ms | 7160 KB | Output is correct |
10 | Correct | 19 ms | 7160 KB | Output is correct |
11 | Correct | 18 ms | 7032 KB | Output is correct |
12 | Correct | 13 ms | 6008 KB | Output is correct |
13 | Correct | 18 ms | 6904 KB | Output is correct |
14 | Correct | 17 ms | 6392 KB | Output is correct |
15 | Correct | 12 ms | 5624 KB | Output is correct |
16 | Correct | 16 ms | 6264 KB | Output is correct |
17 | Correct | 16 ms | 6520 KB | Output is correct |
18 | Correct | 13 ms | 5880 KB | Output is correct |
19 | Correct | 16 ms | 6520 KB | Output is correct |
20 | Correct | 1004 ms | 8552 KB | Output is correct |
21 | Correct | 903 ms | 8452 KB | Output is correct |
22 | Correct | 1004 ms | 8568 KB | Output is correct |
23 | Correct | 1043 ms | 8372 KB | Output is correct |
24 | Correct | 1208 ms | 163516 KB | Output is correct |
25 | Correct | 1267 ms | 170748 KB | Output is correct |
26 | Correct | 1252 ms | 170740 KB | Output is correct |
27 | Correct | 1399 ms | 260440 KB | Output is correct |
28 | Correct | 1393 ms | 260412 KB | Output is correct |
29 | Correct | 1414 ms | 260724 KB | Output is correct |
30 | Correct | 1402 ms | 260328 KB | Output is correct |
31 | Correct | 1413 ms | 251520 KB | Output is correct |
32 | Correct | 1391 ms | 260216 KB | Output is correct |
33 | Correct | 1112 ms | 161984 KB | Output is correct |
34 | Correct | 1024 ms | 133752 KB | Output is correct |
35 | Correct | 1107 ms | 160760 KB | Output is correct |
36 | Correct | 1311 ms | 211168 KB | Output is correct |
37 | Correct | 1261 ms | 192068 KB | Output is correct |
38 | Correct | 1323 ms | 211704 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4988 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Correct | 6 ms | 4984 KB | Output is correct |
4 | Correct | 6 ms | 4984 KB | Output is correct |
5 | Correct | 10 ms | 5360 KB | Output is correct |
6 | Correct | 10 ms | 5368 KB | Output is correct |
7 | Correct | 9 ms | 5368 KB | Output is correct |
8 | Correct | 19 ms | 7280 KB | Output is correct |
9 | Correct | 19 ms | 7160 KB | Output is correct |
10 | Correct | 19 ms | 7160 KB | Output is correct |
11 | Correct | 18 ms | 7032 KB | Output is correct |
12 | Correct | 13 ms | 6008 KB | Output is correct |
13 | Correct | 18 ms | 6904 KB | Output is correct |
14 | Correct | 17 ms | 6392 KB | Output is correct |
15 | Correct | 12 ms | 5624 KB | Output is correct |
16 | Correct | 16 ms | 6264 KB | Output is correct |
17 | Correct | 16 ms | 6520 KB | Output is correct |
18 | Correct | 13 ms | 5880 KB | Output is correct |
19 | Correct | 16 ms | 6520 KB | Output is correct |
20 | Correct | 1004 ms | 8552 KB | Output is correct |
21 | Correct | 903 ms | 8452 KB | Output is correct |
22 | Correct | 1004 ms | 8568 KB | Output is correct |
23 | Correct | 1043 ms | 8372 KB | Output is correct |
24 | Correct | 1208 ms | 163516 KB | Output is correct |
25 | Correct | 1267 ms | 170748 KB | Output is correct |
26 | Correct | 1252 ms | 170740 KB | Output is correct |
27 | Correct | 1399 ms | 260440 KB | Output is correct |
28 | Correct | 1393 ms | 260412 KB | Output is correct |
29 | Correct | 1414 ms | 260724 KB | Output is correct |
30 | Correct | 1402 ms | 260328 KB | Output is correct |
31 | Correct | 1413 ms | 251520 KB | Output is correct |
32 | Correct | 1391 ms | 260216 KB | Output is correct |
33 | Correct | 1112 ms | 161984 KB | Output is correct |
34 | Correct | 1024 ms | 133752 KB | Output is correct |
35 | Correct | 1107 ms | 160760 KB | Output is correct |
36 | Correct | 1311 ms | 211168 KB | Output is correct |
37 | Correct | 1261 ms | 192068 KB | Output is correct |
38 | Correct | 1323 ms | 211704 KB | Output is correct |
39 | Correct | 1258 ms | 165556 KB | Output is correct |
40 | Correct | 1267 ms | 166904 KB | Output is correct |
41 | Correct | 1243 ms | 168144 KB | Output is correct |
42 | Correct | 1227 ms | 167480 KB | Output is correct |
43 | Correct | 1240 ms | 167024 KB | Output is correct |
44 | Correct | 1041 ms | 9108 KB | Output is correct |
45 | Correct | 1020 ms | 8672 KB | Output is correct |
46 | Correct | 1025 ms | 8568 KB | Output is correct |
47 | Correct | 1014 ms | 8436 KB | Output is correct |
48 | Correct | 1006 ms | 8696 KB | Output is correct |
49 | Correct | 1548 ms | 261084 KB | Output is correct |
50 | Correct | 1532 ms | 262824 KB | Output is correct |
51 | Correct | 944 ms | 11128 KB | Output is correct |
52 | Correct | 947 ms | 10232 KB | Output is correct |
53 | Correct | 1412 ms | 213752 KB | Output is correct |
54 | Correct | 1332 ms | 195428 KB | Output is correct |
55 | Correct | 1348 ms | 213060 KB | Output is correct |
56 | Correct | 1260 ms | 194680 KB | Output is correct |
57 | Correct | 1016 ms | 11236 KB | Output is correct |
58 | Correct | 1029 ms | 11256 KB | Output is correct |
59 | Correct | 979 ms | 10376 KB | Output is correct |
60 | Correct | 1034 ms | 10388 KB | Output is correct |
61 | Correct | 1463 ms | 263160 KB | Output is correct |
62 | Correct | 1364 ms | 213948 KB | Output is correct |
63 | Correct | 1250 ms | 194240 KB | Output is correct |
64 | Correct | 1718 ms | 263072 KB | Output is correct |
65 | Correct | 1397 ms | 213096 KB | Output is correct |
66 | Correct | 1283 ms | 194868 KB | Output is correct |
67 | Correct | 1579 ms | 262696 KB | Output is correct |
68 | Correct | 1331 ms | 213624 KB | Output is correct |
69 | Correct | 1242 ms | 192392 KB | Output is correct |
70 | Correct | 1519 ms | 263356 KB | Output is correct |
71 | Correct | 1317 ms | 214020 KB | Output is correct |
72 | Correct | 1294 ms | 194932 KB | Output is correct |
73 | Correct | 1552 ms | 263288 KB | Output is correct |
74 | Correct | 1360 ms | 214136 KB | Output is correct |
75 | Correct | 1285 ms | 195168 KB | Output is correct |
76 | Correct | 1549 ms | 264296 KB | Output is correct |
77 | Correct | 1510 ms | 263148 KB | Output is correct |
78 | Correct | 1412 ms | 263136 KB | Output is correct |
79 | Correct | 983 ms | 11384 KB | Output is correct |
80 | Correct | 926 ms | 10360 KB | Output is correct |
81 | Correct | 915 ms | 9888 KB | Output is correct |
82 | Correct | 1583 ms | 264092 KB | Output is correct |
83 | Correct | 1574 ms | 255464 KB | Output is correct |
84 | Correct | 1519 ms | 262784 KB | Output is correct |
85 | Correct | 1542 ms | 253868 KB | Output is correct |
86 | Correct | 1391 ms | 262972 KB | Output is correct |
87 | Correct | 1435 ms | 254968 KB | Output is correct |
88 | Correct | 1073 ms | 11368 KB | Output is correct |
89 | Correct | 1033 ms | 11384 KB | Output is correct |
90 | Correct | 1031 ms | 10460 KB | Output is correct |
91 | Correct | 1014 ms | 10348 KB | Output is correct |
92 | Correct | 994 ms | 10068 KB | Output is correct |
93 | Correct | 999 ms | 10104 KB | Output is correct |
94 | Correct | 1167 ms | 165660 KB | Output is correct |
95 | Correct | 1206 ms | 136952 KB | Output is correct |
96 | Correct | 1110 ms | 163576 KB | Output is correct |
97 | Correct | 1014 ms | 138272 KB | Output is correct |
98 | Correct | 1099 ms | 164472 KB | Output is correct |
99 | Correct | 1008 ms | 137980 KB | Output is correct |
100 | Correct | 1310 ms | 11448 KB | Output is correct |
101 | Correct | 1082 ms | 11388 KB | Output is correct |
102 | Correct | 1091 ms | 10412 KB | Output is correct |
103 | Correct | 1075 ms | 10616 KB | Output is correct |
104 | Correct | 1097 ms | 10048 KB | Output is correct |
105 | Correct | 1085 ms | 10088 KB | Output is correct |
106 | Correct | 1381 ms | 214264 KB | Output is correct |
107 | Correct | 1291 ms | 195832 KB | Output is correct |
108 | Correct | 1336 ms | 214416 KB | Output is correct |
109 | Correct | 1286 ms | 194552 KB | Output is correct |
110 | Correct | 1315 ms | 214676 KB | Output is correct |
111 | Correct | 1265 ms | 195376 KB | Output is correct |
112 | Correct | 1037 ms | 11384 KB | Output is correct |
113 | Correct | 1030 ms | 11368 KB | Output is correct |
114 | Correct | 1000 ms | 10544 KB | Output is correct |
115 | Correct | 1088 ms | 10592 KB | Output is correct |
116 | Correct | 1008 ms | 10104 KB | Output is correct |
117 | Correct | 1037 ms | 10104 KB | Output is correct |
118 | Correct | 1504 ms | 262544 KB | Output is correct |
119 | Correct | 1341 ms | 214104 KB | Output is correct |
120 | Correct | 1275 ms | 194176 KB | Output is correct |
121 | Correct | 1538 ms | 262680 KB | Output is correct |
122 | Correct | 1332 ms | 213012 KB | Output is correct |
123 | Correct | 1267 ms | 194168 KB | Output is correct |
124 | Correct | 1528 ms | 262776 KB | Output is correct |
125 | Correct | 1320 ms | 214088 KB | Output is correct |
126 | Correct | 1264 ms | 193616 KB | Output is correct |