# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
62724 | 2018-07-29T22:16:02 Z | kingpig9 | Bitaro’s Party (JOI18_bitaro) | C++11 | 13 ms | 8124 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5 + 10; const int SQRT = 320; #define debug(...) fprintf(stderr, __VA_ARGS__) #define fi first #define se second #define all(v) (v).begin(), (v).end() #define fillchar(a, s) memset((a), (s), sizeof(a)) int N, M, Q; vector<int> adj[MAXN], radj[MAXN]; vector<pii> far[MAXN]; //farthest SQRT vertices: pair(dist, vertex) pii tmp[2 * SQRT]; bool vis[MAXN]; void merge (vector<pii> &v, const vector<pii> &w) { int sz = merge(all(v), all(w), tmp, greater<pii> ()) - tmp; v.clear(); for (int i = 0; i < sz && v.size() < SQRT; i++) { if (!vis[tmp[i].se]) { v.push_back(tmp[i]); vis[tmp[i].se] = true; } } for (int i = 0; i < sz; i++) { vis[tmp[i].se] = false; } } bool busy[MAXN]; int dp[MAXN]; int main() { scanf("%d %d %d", &N, &M, &Q); for (int i = 1; i <= M; i++) { int x, y; scanf("%d %d", &x, &y); adj[x].push_back(y); radj[y].push_back(x); } for (int i = 1; i <= N; i++) { far[i].push_back({0, i}); for (int j : radj[i]) { vector<pii> vtmp = far[j]; for (pii &p : vtmp) { p.fi++; } merge(far[i], vtmp); } } //if size >= SQRT then brute force for (int qi = 1; qi <= Q; qi++) { int x, sz; scanf("%d %d", &x, &sz); vector<int> vbusy(sz); for (int &c : vbusy) { scanf("%d", &c); busy[c] = true; } int ans = -1; if (sz < SQRT) { //the farthest away -- one of them will not be for (pii p : far[x]) { if (!busy[p.se]) { ans = p.fi; break; } } } else { //brute force for (int i = x; i >= 1; i--) { dp[i] = 0; } for (int i = x; i >= 1; i--) { for (int j : radj[i]) { dp[j] = max(dp[j], dp[i] + 1); } if (!busy[i]) { ans = max(ans, dp[i]); } } } printf("%d\n", ans); for (int c : vbusy) { busy[c] = false; } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 7288 KB | Output is correct |
2 | Correct | 9 ms | 7412 KB | Output is correct |
3 | Correct | 10 ms | 7488 KB | Output is correct |
4 | Correct | 11 ms | 7692 KB | Output is correct |
5 | Incorrect | 13 ms | 8124 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 7288 KB | Output is correct |
2 | Correct | 9 ms | 7412 KB | Output is correct |
3 | Correct | 10 ms | 7488 KB | Output is correct |
4 | Correct | 11 ms | 7692 KB | Output is correct |
5 | Incorrect | 13 ms | 8124 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 7288 KB | Output is correct |
2 | Correct | 9 ms | 7412 KB | Output is correct |
3 | Correct | 10 ms | 7488 KB | Output is correct |
4 | Correct | 11 ms | 7692 KB | Output is correct |
5 | Incorrect | 13 ms | 8124 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |