# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
238331 | 2020-06-10T19:04:24 Z | Charis02 | Bitaro’s Party (JOI18_bitaro) | C++14 | 1806 ms | 171128 KB |
#include<iostream> #include<stdio.h> #include<vector> #include<cmath> #include<queue> #include<string.h> #include<map> #include<unordered_set> #include<algorithm> #define pi pair < int,int > #define mp(a,b) make_pair(a,b) #define mid (low+high)/2 #define rep(i,a,b) for(int i = a;i < b;i++) #define N 100004 using namespace std; int n,m,q; vector < pi > longest[N]; bool used[N]; vector < int > graph[N]; unordered_set < int > busy; int root; int curtime; int last[N],dp[N]; void merge_lists(vector < pi > &result,const vector < pi > &add) { vector < pi > r; r.clear(); int p1 = 0; int p2 = 0; while((p1 < result.size() || p2 < add.size()) && r.size() < root) { if(p1 == result.size()) { if(!used[add[p2].second]) r.push_back(mp(add[p2].first+1,add[p2].second)); used[add[p2].second] = true; p2++; } else if(p2 == add.size()) { if(!used[result[p1].second]) r.push_back(result[p1]); used[result[p1].second] = true; p1++; } else if(result[p1].first < add[p2].first+1) { if(!used[add[p2].second]) r.push_back(mp(add[p2].first+1,add[p2].second)); used[add[p2].second]=true; p2++; } else { if(!used[result[p1].second]) r.push_back(result[p1]); used[result[p1].second]=true; p1++; } } result = r; rep(i,0,result.size()) used[result[i].second]=false; return; } void precalc() { rep(i,1,n+1) longest[i].push_back(mp(0,i)); rep(i,1,n+1) { rep(j,0,graph[i].size()) { int v = graph[i][j]; merge_lists(longest[v],longest[i]); } } return; } int solve_smart(int target) { dp[target]=-1; if(busy.count(target)==0) dp[target] = 0; rep(i,1,target) { if(last[i] != curtime) { if(busy.count(i) != 0) continue; dp[i] = 0; } last[i] = curtime; rep(j,0,graph[i].size()) { int v = graph[i][j]; if(last[v] != curtime) dp[v] = -1; dp[v]=max(dp[i]+1,dp[v]); last[v]=curtime; } } return dp[target]; } int solve_simple(int target) { rep(i,0,longest[target].size()) { if(busy.count(longest[target][i].second) == 0) return longest[target][i].first; } return -1; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> q; root = 200; rep(i,0,m) { int a,b; cin >> a >> b; graph[a].push_back(b); } precalc(); rep(i,0,q) { curtime=i+1; int t,y,a; busy.clear(); cin >> t >> y; rep(j,0,y) { cin >> a; busy.insert(a); } if(y >= root) cout << solve_smart(t) << "\n"; else cout << solve_simple(t) << "\n"; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 4992 KB | Output is correct |
2 | Correct | 8 ms | 4992 KB | Output is correct |
3 | Correct | 8 ms | 5120 KB | Output is correct |
4 | Correct | 7 ms | 4992 KB | Output is correct |
5 | Correct | 11 ms | 5504 KB | Output is correct |
6 | Correct | 11 ms | 5504 KB | Output is correct |
7 | Correct | 10 ms | 5376 KB | Output is correct |
8 | Correct | 16 ms | 6656 KB | Output is correct |
9 | Correct | 15 ms | 6656 KB | Output is correct |
10 | Correct | 17 ms | 6656 KB | Output is correct |
11 | Correct | 15 ms | 6528 KB | Output is correct |
12 | Correct | 13 ms | 6016 KB | Output is correct |
13 | Correct | 15 ms | 6528 KB | Output is correct |
14 | Correct | 14 ms | 6016 KB | Output is correct |
15 | Correct | 12 ms | 5632 KB | Output is correct |
16 | Correct | 14 ms | 5888 KB | Output is correct |
17 | Correct | 14 ms | 6144 KB | Output is correct |
18 | Correct | 13 ms | 5760 KB | Output is correct |
19 | Correct | 14 ms | 6272 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 4992 KB | Output is correct |
2 | Correct | 8 ms | 4992 KB | Output is correct |
3 | Correct | 8 ms | 5120 KB | Output is correct |
4 | Correct | 7 ms | 4992 KB | Output is correct |
5 | Correct | 11 ms | 5504 KB | Output is correct |
6 | Correct | 11 ms | 5504 KB | Output is correct |
7 | Correct | 10 ms | 5376 KB | Output is correct |
8 | Correct | 16 ms | 6656 KB | Output is correct |
9 | Correct | 15 ms | 6656 KB | Output is correct |
10 | Correct | 17 ms | 6656 KB | Output is correct |
11 | Correct | 15 ms | 6528 KB | Output is correct |
12 | Correct | 13 ms | 6016 KB | Output is correct |
13 | Correct | 15 ms | 6528 KB | Output is correct |
14 | Correct | 14 ms | 6016 KB | Output is correct |
15 | Correct | 12 ms | 5632 KB | Output is correct |
16 | Correct | 14 ms | 5888 KB | Output is correct |
17 | Correct | 14 ms | 6144 KB | Output is correct |
18 | Correct | 13 ms | 5760 KB | Output is correct |
19 | Correct | 14 ms | 6272 KB | Output is correct |
20 | Correct | 734 ms | 8184 KB | Output is correct |
21 | Correct | 709 ms | 8252 KB | Output is correct |
22 | Correct | 707 ms | 8316 KB | Output is correct |
23 | Correct | 944 ms | 8184 KB | Output is correct |
24 | Correct | 973 ms | 122980 KB | Output is correct |
25 | Correct | 967 ms | 126564 KB | Output is correct |
26 | Correct | 975 ms | 126360 KB | Output is correct |
27 | Correct | 1095 ms | 169316 KB | Output is correct |
28 | Correct | 1125 ms | 169192 KB | Output is correct |
29 | Correct | 1070 ms | 168808 KB | Output is correct |
30 | Correct | 1041 ms | 168548 KB | Output is correct |
31 | Correct | 1066 ms | 165924 KB | Output is correct |
32 | Correct | 1074 ms | 167780 KB | Output is correct |
33 | Correct | 791 ms | 108968 KB | Output is correct |
34 | Correct | 753 ms | 94540 KB | Output is correct |
35 | Correct | 805 ms | 108388 KB | Output is correct |
36 | Correct | 981 ms | 140644 KB | Output is correct |
37 | Correct | 861 ms | 131296 KB | Output is correct |
38 | Correct | 958 ms | 140276 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 4992 KB | Output is correct |
2 | Correct | 8 ms | 4992 KB | Output is correct |
3 | Correct | 8 ms | 5120 KB | Output is correct |
4 | Correct | 7 ms | 4992 KB | Output is correct |
5 | Correct | 11 ms | 5504 KB | Output is correct |
6 | Correct | 11 ms | 5504 KB | Output is correct |
7 | Correct | 10 ms | 5376 KB | Output is correct |
8 | Correct | 16 ms | 6656 KB | Output is correct |
9 | Correct | 15 ms | 6656 KB | Output is correct |
10 | Correct | 17 ms | 6656 KB | Output is correct |
11 | Correct | 15 ms | 6528 KB | Output is correct |
12 | Correct | 13 ms | 6016 KB | Output is correct |
13 | Correct | 15 ms | 6528 KB | Output is correct |
14 | Correct | 14 ms | 6016 KB | Output is correct |
15 | Correct | 12 ms | 5632 KB | Output is correct |
16 | Correct | 14 ms | 5888 KB | Output is correct |
17 | Correct | 14 ms | 6144 KB | Output is correct |
18 | Correct | 13 ms | 5760 KB | Output is correct |
19 | Correct | 14 ms | 6272 KB | Output is correct |
20 | Correct | 734 ms | 8184 KB | Output is correct |
21 | Correct | 709 ms | 8252 KB | Output is correct |
22 | Correct | 707 ms | 8316 KB | Output is correct |
23 | Correct | 944 ms | 8184 KB | Output is correct |
24 | Correct | 973 ms | 122980 KB | Output is correct |
25 | Correct | 967 ms | 126564 KB | Output is correct |
26 | Correct | 975 ms | 126360 KB | Output is correct |
27 | Correct | 1095 ms | 169316 KB | Output is correct |
28 | Correct | 1125 ms | 169192 KB | Output is correct |
29 | Correct | 1070 ms | 168808 KB | Output is correct |
30 | Correct | 1041 ms | 168548 KB | Output is correct |
31 | Correct | 1066 ms | 165924 KB | Output is correct |
32 | Correct | 1074 ms | 167780 KB | Output is correct |
33 | Correct | 791 ms | 108968 KB | Output is correct |
34 | Correct | 753 ms | 94540 KB | Output is correct |
35 | Correct | 805 ms | 108388 KB | Output is correct |
36 | Correct | 981 ms | 140644 KB | Output is correct |
37 | Correct | 861 ms | 131296 KB | Output is correct |
38 | Correct | 958 ms | 140276 KB | Output is correct |
39 | Correct | 945 ms | 122776 KB | Output is correct |
40 | Correct | 905 ms | 123888 KB | Output is correct |
41 | Correct | 983 ms | 124152 KB | Output is correct |
42 | Correct | 1272 ms | 125176 KB | Output is correct |
43 | Correct | 929 ms | 124408 KB | Output is correct |
44 | Correct | 779 ms | 8680 KB | Output is correct |
45 | Correct | 742 ms | 8184 KB | Output is correct |
46 | Correct | 730 ms | 8312 KB | Output is correct |
47 | Correct | 822 ms | 8316 KB | Output is correct |
48 | Correct | 800 ms | 8312 KB | Output is correct |
49 | Correct | 1165 ms | 167544 KB | Output is correct |
50 | Correct | 1140 ms | 166808 KB | Output is correct |
51 | Correct | 739 ms | 8696 KB | Output is correct |
52 | Correct | 715 ms | 8312 KB | Output is correct |
53 | Correct | 1072 ms | 139128 KB | Output is correct |
54 | Correct | 933 ms | 130564 KB | Output is correct |
55 | Correct | 971 ms | 139000 KB | Output is correct |
56 | Correct | 913 ms | 130424 KB | Output is correct |
57 | Correct | 761 ms | 8568 KB | Output is correct |
58 | Correct | 792 ms | 8696 KB | Output is correct |
59 | Correct | 725 ms | 8184 KB | Output is correct |
60 | Correct | 749 ms | 8212 KB | Output is correct |
61 | Correct | 1297 ms | 167784 KB | Output is correct |
62 | Correct | 1159 ms | 140452 KB | Output is correct |
63 | Correct | 1105 ms | 130612 KB | Output is correct |
64 | Correct | 1651 ms | 167800 KB | Output is correct |
65 | Correct | 1772 ms | 142328 KB | Output is correct |
66 | Correct | 1598 ms | 134008 KB | Output is correct |
67 | Correct | 1806 ms | 170392 KB | Output is correct |
68 | Correct | 1629 ms | 142712 KB | Output is correct |
69 | Correct | 1383 ms | 132204 KB | Output is correct |
70 | Correct | 1097 ms | 170492 KB | Output is correct |
71 | Correct | 979 ms | 142944 KB | Output is correct |
72 | Correct | 927 ms | 133752 KB | Output is correct |
73 | Correct | 1214 ms | 170568 KB | Output is correct |
74 | Correct | 1127 ms | 142840 KB | Output is correct |
75 | Correct | 963 ms | 133496 KB | Output is correct |
76 | Correct | 1137 ms | 171128 KB | Output is correct |
77 | Correct | 1249 ms | 170488 KB | Output is correct |
78 | Correct | 1151 ms | 170804 KB | Output is correct |
79 | Correct | 771 ms | 11000 KB | Output is correct |
80 | Correct | 736 ms | 10212 KB | Output is correct |
81 | Correct | 729 ms | 9736 KB | Output is correct |
82 | Correct | 1175 ms | 170488 KB | Output is correct |
83 | Correct | 1092 ms | 168824 KB | Output is correct |
84 | Correct | 1145 ms | 169860 KB | Output is correct |
85 | Correct | 1136 ms | 168184 KB | Output is correct |
86 | Correct | 1117 ms | 170164 KB | Output is correct |
87 | Correct | 1339 ms | 168624 KB | Output is correct |
88 | Correct | 769 ms | 11256 KB | Output is correct |
89 | Correct | 796 ms | 11128 KB | Output is correct |
90 | Correct | 759 ms | 10104 KB | Output is correct |
91 | Correct | 769 ms | 10232 KB | Output is correct |
92 | Correct | 741 ms | 9976 KB | Output is correct |
93 | Correct | 734 ms | 9848 KB | Output is correct |
94 | Correct | 888 ms | 111864 KB | Output is correct |
95 | Correct | 743 ms | 96936 KB | Output is correct |
96 | Correct | 940 ms | 110968 KB | Output is correct |
97 | Correct | 828 ms | 98332 KB | Output is correct |
98 | Correct | 888 ms | 111412 KB | Output is correct |
99 | Correct | 735 ms | 98232 KB | Output is correct |
100 | Correct | 995 ms | 11040 KB | Output is correct |
101 | Correct | 969 ms | 11000 KB | Output is correct |
102 | Correct | 961 ms | 10232 KB | Output is correct |
103 | Correct | 977 ms | 10232 KB | Output is correct |
104 | Correct | 964 ms | 9848 KB | Output is correct |
105 | Correct | 969 ms | 9784 KB | Output is correct |
106 | Correct | 1008 ms | 142712 KB | Output is correct |
107 | Correct | 990 ms | 134136 KB | Output is correct |
108 | Correct | 1028 ms | 143224 KB | Output is correct |
109 | Correct | 991 ms | 133368 KB | Output is correct |
110 | Correct | 951 ms | 143636 KB | Output is correct |
111 | Correct | 984 ms | 134436 KB | Output is correct |
112 | Correct | 757 ms | 11128 KB | Output is correct |
113 | Correct | 779 ms | 11204 KB | Output is correct |
114 | Correct | 739 ms | 10104 KB | Output is correct |
115 | Correct | 747 ms | 10164 KB | Output is correct |
116 | Correct | 728 ms | 9848 KB | Output is correct |
117 | Correct | 745 ms | 9848 KB | Output is correct |
118 | Correct | 1066 ms | 169524 KB | Output is correct |
119 | Correct | 972 ms | 142200 KB | Output is correct |
120 | Correct | 862 ms | 132348 KB | Output is correct |
121 | Correct | 1087 ms | 169592 KB | Output is correct |
122 | Correct | 946 ms | 141684 KB | Output is correct |
123 | Correct | 875 ms | 132216 KB | Output is correct |
124 | Correct | 1113 ms | 169592 KB | Output is correct |
125 | Correct | 963 ms | 142328 KB | Output is correct |
126 | Correct | 851 ms | 132100 KB | Output is correct |