# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
47810 | 2018-05-07T14:12:56 Z | mirbek01 | Bitaro’s Party (JOI18_bitaro) | C++17 | 1598 ms | 211476 KB |
# include <bits/stdc++.h> using namespace std; const int N = 1e5 + 2; const int B = 200; int n, m, q, used[N], dp[N]; vector <int> g[N]; vector < pair <int, int> > vd[N]; vector < pair <int, int> > get(vector < pair <int, int> > a, vector < pair <int, int> > b){ vector < pair <int, int> > res; for(int i = 0; i < b.size(); i ++) b[i].first ++; int i = 0, j = 0; while(i < a.size() && j < b.size() && res.size() <= B){ pair <int, int> p; if(a[i].first > b[j].first){ p = a[i ++]; } else { p = b[j ++]; } if(!used[p.second]){ res.push_back(p); used[p.second] = 1; } } while(i < a.size() && res.size() <= B){ pair <int, int> p = a[i ++]; if(!used[p.second]){ res.push_back(p); used[p.second] = 1; } } while(j < b.size() && res.size() <= B){ pair <int, int> p = b[j ++]; if(!used[p.second]){ res.push_back(p); used[p.second] = 1; } } for(int i = 0; i < res.size(); i ++) used[res[i].second] = 0; return res; } int main(){ scanf("%d %d %d", &n, &m, &q); for(int i = 1; i <= m; i ++){ int u, v; scanf("%d %d", &u, &v); g[v].emplace_back(u); } for(int i = 1; i <= n; i ++){ vd[i].push_back({0, i}); for(int to : g[i]){ vd[i] = get(vd[i], vd[to]); } } while(q --){ int t, y; vector <int> v; scanf("%d %d", &t, &y); for(int i = 1; i <= y; i ++){ int x; scanf("%d", &x); used[x] = 1; v.emplace_back(x); } if(y >= B){ for(int i = 1; i <= t; i ++){ dp[i] = 0; for(int to : g[i]){ used[i] = min(used[to], used[i]); if(!used[to]){ dp[i] = max(dp[i], dp[to] + 1); } } } if(used[t]) dp[t] --; printf("%d\n", dp[t]); } else { int ans = -1; for(int i = 0; i < vd[t].size(); i ++){ int f = vd[t][i].first, s = vd[t][i].second; if(used[s]) continue; ans = max(ans, f); } printf("%d\n", ans); } for(int i : v) used[i] = 0; } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 5236 KB | Output is correct |
3 | Correct | 6 ms | 5236 KB | Output is correct |
4 | Correct | 8 ms | 5236 KB | Output is correct |
5 | Correct | 10 ms | 5632 KB | Output is correct |
6 | Correct | 11 ms | 5692 KB | Output is correct |
7 | Correct | 11 ms | 5692 KB | Output is correct |
8 | Correct | 16 ms | 7232 KB | Output is correct |
9 | Correct | 16 ms | 7232 KB | Output is correct |
10 | Correct | 16 ms | 7232 KB | Output is correct |
11 | Correct | 15 ms | 7232 KB | Output is correct |
12 | Correct | 8 ms | 7232 KB | Output is correct |
13 | Correct | 15 ms | 7232 KB | Output is correct |
14 | Correct | 15 ms | 7232 KB | Output is correct |
15 | Correct | 13 ms | 7232 KB | Output is correct |
16 | Correct | 15 ms | 7232 KB | Output is correct |
17 | Correct | 16 ms | 7232 KB | Output is correct |
18 | Correct | 13 ms | 7232 KB | Output is correct |
19 | Correct | 15 ms | 7232 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 5236 KB | Output is correct |
3 | Correct | 6 ms | 5236 KB | Output is correct |
4 | Correct | 8 ms | 5236 KB | Output is correct |
5 | Correct | 10 ms | 5632 KB | Output is correct |
6 | Correct | 11 ms | 5692 KB | Output is correct |
7 | Correct | 11 ms | 5692 KB | Output is correct |
8 | Correct | 16 ms | 7232 KB | Output is correct |
9 | Correct | 16 ms | 7232 KB | Output is correct |
10 | Correct | 16 ms | 7232 KB | Output is correct |
11 | Correct | 15 ms | 7232 KB | Output is correct |
12 | Correct | 8 ms | 7232 KB | Output is correct |
13 | Correct | 15 ms | 7232 KB | Output is correct |
14 | Correct | 15 ms | 7232 KB | Output is correct |
15 | Correct | 13 ms | 7232 KB | Output is correct |
16 | Correct | 15 ms | 7232 KB | Output is correct |
17 | Correct | 16 ms | 7232 KB | Output is correct |
18 | Correct | 13 ms | 7232 KB | Output is correct |
19 | Correct | 15 ms | 7232 KB | Output is correct |
20 | Correct | 866 ms | 8236 KB | Output is correct |
21 | Correct | 884 ms | 8236 KB | Output is correct |
22 | Correct | 891 ms | 8236 KB | Output is correct |
23 | Correct | 833 ms | 8324 KB | Output is correct |
24 | Correct | 1169 ms | 151288 KB | Output is correct |
25 | Correct | 1126 ms | 155620 KB | Output is correct |
26 | Correct | 1132 ms | 155912 KB | Output is correct |
27 | Correct | 1199 ms | 211280 KB | Output is correct |
28 | Correct | 1181 ms | 211432 KB | Output is correct |
29 | Correct | 1207 ms | 211432 KB | Output is correct |
30 | Correct | 1263 ms | 211432 KB | Output is correct |
31 | Correct | 1312 ms | 211432 KB | Output is correct |
32 | Correct | 1259 ms | 211432 KB | Output is correct |
33 | Correct | 991 ms | 211432 KB | Output is correct |
34 | Correct | 955 ms | 211432 KB | Output is correct |
35 | Correct | 946 ms | 211432 KB | Output is correct |
36 | Correct | 1075 ms | 211432 KB | Output is correct |
37 | Correct | 1106 ms | 211432 KB | Output is correct |
38 | Correct | 1104 ms | 211432 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 5236 KB | Output is correct |
3 | Correct | 6 ms | 5236 KB | Output is correct |
4 | Correct | 8 ms | 5236 KB | Output is correct |
5 | Correct | 10 ms | 5632 KB | Output is correct |
6 | Correct | 11 ms | 5692 KB | Output is correct |
7 | Correct | 11 ms | 5692 KB | Output is correct |
8 | Correct | 16 ms | 7232 KB | Output is correct |
9 | Correct | 16 ms | 7232 KB | Output is correct |
10 | Correct | 16 ms | 7232 KB | Output is correct |
11 | Correct | 15 ms | 7232 KB | Output is correct |
12 | Correct | 8 ms | 7232 KB | Output is correct |
13 | Correct | 15 ms | 7232 KB | Output is correct |
14 | Correct | 15 ms | 7232 KB | Output is correct |
15 | Correct | 13 ms | 7232 KB | Output is correct |
16 | Correct | 15 ms | 7232 KB | Output is correct |
17 | Correct | 16 ms | 7232 KB | Output is correct |
18 | Correct | 13 ms | 7232 KB | Output is correct |
19 | Correct | 15 ms | 7232 KB | Output is correct |
20 | Correct | 866 ms | 8236 KB | Output is correct |
21 | Correct | 884 ms | 8236 KB | Output is correct |
22 | Correct | 891 ms | 8236 KB | Output is correct |
23 | Correct | 833 ms | 8324 KB | Output is correct |
24 | Correct | 1169 ms | 151288 KB | Output is correct |
25 | Correct | 1126 ms | 155620 KB | Output is correct |
26 | Correct | 1132 ms | 155912 KB | Output is correct |
27 | Correct | 1199 ms | 211280 KB | Output is correct |
28 | Correct | 1181 ms | 211432 KB | Output is correct |
29 | Correct | 1207 ms | 211432 KB | Output is correct |
30 | Correct | 1263 ms | 211432 KB | Output is correct |
31 | Correct | 1312 ms | 211432 KB | Output is correct |
32 | Correct | 1259 ms | 211432 KB | Output is correct |
33 | Correct | 991 ms | 211432 KB | Output is correct |
34 | Correct | 955 ms | 211432 KB | Output is correct |
35 | Correct | 946 ms | 211432 KB | Output is correct |
36 | Correct | 1075 ms | 211432 KB | Output is correct |
37 | Correct | 1106 ms | 211432 KB | Output is correct |
38 | Correct | 1104 ms | 211432 KB | Output is correct |
39 | Correct | 1403 ms | 211432 KB | Output is correct |
40 | Correct | 1211 ms | 211432 KB | Output is correct |
41 | Correct | 1198 ms | 211432 KB | Output is correct |
42 | Correct | 1391 ms | 211432 KB | Output is correct |
43 | Correct | 1191 ms | 211432 KB | Output is correct |
44 | Correct | 945 ms | 211432 KB | Output is correct |
45 | Correct | 880 ms | 211432 KB | Output is correct |
46 | Correct | 857 ms | 211432 KB | Output is correct |
47 | Correct | 874 ms | 211432 KB | Output is correct |
48 | Correct | 833 ms | 211432 KB | Output is correct |
49 | Correct | 1341 ms | 211432 KB | Output is correct |
50 | Correct | 1160 ms | 211432 KB | Output is correct |
51 | Correct | 909 ms | 211432 KB | Output is correct |
52 | Correct | 845 ms | 211432 KB | Output is correct |
53 | Correct | 1207 ms | 211432 KB | Output is correct |
54 | Correct | 1212 ms | 211432 KB | Output is correct |
55 | Correct | 1084 ms | 211432 KB | Output is correct |
56 | Correct | 1083 ms | 211432 KB | Output is correct |
57 | Correct | 929 ms | 211432 KB | Output is correct |
58 | Correct | 901 ms | 211432 KB | Output is correct |
59 | Correct | 843 ms | 211432 KB | Output is correct |
60 | Correct | 866 ms | 211432 KB | Output is correct |
61 | Correct | 1236 ms | 211432 KB | Output is correct |
62 | Correct | 1229 ms | 211432 KB | Output is correct |
63 | Correct | 1177 ms | 211432 KB | Output is correct |
64 | Correct | 1590 ms | 211432 KB | Output is correct |
65 | Correct | 1407 ms | 211432 KB | Output is correct |
66 | Correct | 1598 ms | 211432 KB | Output is correct |
67 | Correct | 1573 ms | 211432 KB | Output is correct |
68 | Correct | 1522 ms | 211432 KB | Output is correct |
69 | Correct | 1514 ms | 211432 KB | Output is correct |
70 | Correct | 1203 ms | 211432 KB | Output is correct |
71 | Correct | 1095 ms | 211432 KB | Output is correct |
72 | Correct | 1084 ms | 211432 KB | Output is correct |
73 | Correct | 1218 ms | 211432 KB | Output is correct |
74 | Correct | 1234 ms | 211432 KB | Output is correct |
75 | Correct | 1192 ms | 211432 KB | Output is correct |
76 | Correct | 1474 ms | 211432 KB | Output is correct |
77 | Correct | 1367 ms | 211476 KB | Output is correct |
78 | Correct | 1235 ms | 211476 KB | Output is correct |
79 | Correct | 902 ms | 211476 KB | Output is correct |
80 | Correct | 852 ms | 211476 KB | Output is correct |
81 | Correct | 863 ms | 211476 KB | Output is correct |
82 | Correct | 1565 ms | 211476 KB | Output is correct |
83 | Correct | 1582 ms | 211476 KB | Output is correct |
84 | Correct | 1431 ms | 211476 KB | Output is correct |
85 | Correct | 1456 ms | 211476 KB | Output is correct |
86 | Correct | 1311 ms | 211476 KB | Output is correct |
87 | Correct | 1394 ms | 211476 KB | Output is correct |
88 | Correct | 933 ms | 211476 KB | Output is correct |
89 | Correct | 951 ms | 211476 KB | Output is correct |
90 | Correct | 896 ms | 211476 KB | Output is correct |
91 | Correct | 879 ms | 211476 KB | Output is correct |
92 | Correct | 875 ms | 211476 KB | Output is correct |
93 | Correct | 862 ms | 211476 KB | Output is correct |
94 | Correct | 1194 ms | 211476 KB | Output is correct |
95 | Correct | 1192 ms | 211476 KB | Output is correct |
96 | Correct | 1058 ms | 211476 KB | Output is correct |
97 | Correct | 1020 ms | 211476 KB | Output is correct |
98 | Correct | 1073 ms | 211476 KB | Output is correct |
99 | Correct | 940 ms | 211476 KB | Output is correct |
100 | Correct | 971 ms | 211476 KB | Output is correct |
101 | Correct | 880 ms | 211476 KB | Output is correct |
102 | Correct | 831 ms | 211476 KB | Output is correct |
103 | Correct | 828 ms | 211476 KB | Output is correct |
104 | Correct | 848 ms | 211476 KB | Output is correct |
105 | Correct | 854 ms | 211476 KB | Output is correct |
106 | Correct | 1313 ms | 211476 KB | Output is correct |
107 | Correct | 1322 ms | 211476 KB | Output is correct |
108 | Correct | 1171 ms | 211476 KB | Output is correct |
109 | Correct | 1094 ms | 211476 KB | Output is correct |
110 | Correct | 1092 ms | 211476 KB | Output is correct |
111 | Correct | 1087 ms | 211476 KB | Output is correct |
112 | Correct | 959 ms | 211476 KB | Output is correct |
113 | Correct | 947 ms | 211476 KB | Output is correct |
114 | Correct | 863 ms | 211476 KB | Output is correct |
115 | Correct | 862 ms | 211476 KB | Output is correct |
116 | Correct | 850 ms | 211476 KB | Output is correct |
117 | Correct | 854 ms | 211476 KB | Output is correct |
118 | Correct | 1243 ms | 211476 KB | Output is correct |
119 | Correct | 1154 ms | 211476 KB | Output is correct |
120 | Correct | 1067 ms | 211476 KB | Output is correct |
121 | Correct | 1159 ms | 211476 KB | Output is correct |
122 | Correct | 1114 ms | 211476 KB | Output is correct |
123 | Correct | 1109 ms | 211476 KB | Output is correct |
124 | Correct | 1273 ms | 211476 KB | Output is correct |
125 | Correct | 1090 ms | 211476 KB | Output is correct |
126 | Correct | 1123 ms | 211476 KB | Output is correct |