# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
521186 | 2022-02-01T07:45:53 Z | Ai7081 | Bitaro’s Party (JOI18_bitaro) | C++17 | 1936 ms | 524292 KB |
#include <bits/stdc++.h> using namespace std; const int N = 100005; struct Query{ int town, idx; vector<int> busy; bool operator < (const Query &o) const { return town < o.town; } }; int dp[N], out[N]; set<pair<int, int>, greater<pair<int, int>>> s[N]; set<int, greater<int>> rev[N]; vector<int> adj[N]; vector<Query> que; int main() { int n, m, Q, a, b, n_busy; scanf(" %d %d %d", &n, &m, &Q); int sq = ceil(sqrt(n+.0)); while (m--) { scanf(" %d %d", &a, &b); rev[max(a, b)].insert(min(a, b)); adj[min(a, b)].push_back(max(a, b)); } for (int i=1; i<=Q; i++) { Query in; in.idx = i; scanf(" %d %d", &in.town, &n_busy); while (n_busy--) { scanf(" %d", &a); in.busy.push_back(a); } que.push_back(in); } sort(que.begin(), que.end()); int now = 1; for (int i=1; i<=n; i++) s[i].insert({0, i}); fill_n(out, n+5, -1); for (auto q : que) { while (now < q.town) { now++; for (auto to : rev[now]) { for (auto [val, from] : s[to]) { if (s[now].size() < sq) s[now].insert({val+1, from}); else if (val+1 > (--s[now].end())->first) { s[now].erase(--s[now].end()); s[now].insert({val+1, from}); } else break; } } } if (q.busy.size() >= sq) { fill_n(dp, q.town+5, 0); for (auto it : q.busy) dp[it] = -1; for (int i=1; i<=q.town; i++) { if (dp[i] == -1) continue; for (auto to : adj[i]) dp[to] = max(dp[to], dp[i] + 1); } out[q.idx] = dp[q.town]; } else { for (auto [val, from] : s[now]) { auto tmp = lower_bound(q.busy.begin(), q.busy.end(), from); if (tmp == q.busy.end() || *tmp != from) { out[q.idx] = val; break; } } } } for (int i=1; i<=Q; i++) printf("%d\n", out[i]); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11980 KB | Output is correct |
2 | Correct | 6 ms | 12040 KB | Output is correct |
3 | Correct | 6 ms | 11980 KB | Output is correct |
4 | Correct | 6 ms | 12044 KB | Output is correct |
5 | Correct | 11 ms | 12452 KB | Output is correct |
6 | Correct | 13 ms | 13188 KB | Output is correct |
7 | Correct | 11 ms | 13132 KB | Output is correct |
8 | Correct | 9 ms | 12492 KB | Output is correct |
9 | Correct | 9 ms | 13080 KB | Output is correct |
10 | Correct | 9 ms | 13004 KB | Output is correct |
11 | Correct | 7 ms | 12236 KB | Output is correct |
12 | Correct | 7 ms | 12320 KB | Output is correct |
13 | Correct | 7 ms | 12248 KB | Output is correct |
14 | Correct | 7 ms | 12236 KB | Output is correct |
15 | Correct | 7 ms | 12236 KB | Output is correct |
16 | Correct | 9 ms | 12952 KB | Output is correct |
17 | Correct | 8 ms | 12620 KB | Output is correct |
18 | Correct | 10 ms | 12248 KB | Output is correct |
19 | Correct | 13 ms | 13296 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11980 KB | Output is correct |
2 | Correct | 6 ms | 12040 KB | Output is correct |
3 | Correct | 6 ms | 11980 KB | Output is correct |
4 | Correct | 6 ms | 12044 KB | Output is correct |
5 | Correct | 11 ms | 12452 KB | Output is correct |
6 | Correct | 13 ms | 13188 KB | Output is correct |
7 | Correct | 11 ms | 13132 KB | Output is correct |
8 | Correct | 9 ms | 12492 KB | Output is correct |
9 | Correct | 9 ms | 13080 KB | Output is correct |
10 | Correct | 9 ms | 13004 KB | Output is correct |
11 | Correct | 7 ms | 12236 KB | Output is correct |
12 | Correct | 7 ms | 12320 KB | Output is correct |
13 | Correct | 7 ms | 12248 KB | Output is correct |
14 | Correct | 7 ms | 12236 KB | Output is correct |
15 | Correct | 7 ms | 12236 KB | Output is correct |
16 | Correct | 9 ms | 12952 KB | Output is correct |
17 | Correct | 8 ms | 12620 KB | Output is correct |
18 | Correct | 10 ms | 12248 KB | Output is correct |
19 | Correct | 13 ms | 13296 KB | Output is correct |
20 | Correct | 138 ms | 24728 KB | Output is correct |
21 | Correct | 135 ms | 24308 KB | Output is correct |
22 | Correct | 137 ms | 25332 KB | Output is correct |
23 | Correct | 126 ms | 24388 KB | Output is correct |
24 | Runtime error | 1936 ms | 524292 KB | Execution killed with signal 9 |
25 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11980 KB | Output is correct |
2 | Correct | 6 ms | 12040 KB | Output is correct |
3 | Correct | 6 ms | 11980 KB | Output is correct |
4 | Correct | 6 ms | 12044 KB | Output is correct |
5 | Correct | 11 ms | 12452 KB | Output is correct |
6 | Correct | 13 ms | 13188 KB | Output is correct |
7 | Correct | 11 ms | 13132 KB | Output is correct |
8 | Correct | 9 ms | 12492 KB | Output is correct |
9 | Correct | 9 ms | 13080 KB | Output is correct |
10 | Correct | 9 ms | 13004 KB | Output is correct |
11 | Correct | 7 ms | 12236 KB | Output is correct |
12 | Correct | 7 ms | 12320 KB | Output is correct |
13 | Correct | 7 ms | 12248 KB | Output is correct |
14 | Correct | 7 ms | 12236 KB | Output is correct |
15 | Correct | 7 ms | 12236 KB | Output is correct |
16 | Correct | 9 ms | 12952 KB | Output is correct |
17 | Correct | 8 ms | 12620 KB | Output is correct |
18 | Correct | 10 ms | 12248 KB | Output is correct |
19 | Correct | 13 ms | 13296 KB | Output is correct |
20 | Correct | 138 ms | 24728 KB | Output is correct |
21 | Correct | 135 ms | 24308 KB | Output is correct |
22 | Correct | 137 ms | 25332 KB | Output is correct |
23 | Correct | 126 ms | 24388 KB | Output is correct |
24 | Runtime error | 1936 ms | 524292 KB | Execution killed with signal 9 |
25 | Halted | 0 ms | 0 KB | - |