# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
83868 | 2018-11-11T13:08:41 Z | win11905 | Bitaro’s Party (JOI18_bitaro) | C++11 | 2000 ms | 27312 KB |
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define pii pair<int, int> #define x first #define y second using namespace std; const int N = 1e5+5; const int INF = 1e9; const int sz = 350; int n, m, q; vector<int> g[N], topo; vector<pii> block[N]; int pos[N], deg[N]; int d[N]; map<int, int> tod[N]; bool mark[N]; int main() { scanf("%d %d %d", &n, &m, &q); for(int i = 0, u, v; i < m; ++i) { scanf("%d %d", &u, &v); if(u > v) swap(u, v); g[u].emplace_back(v); deg[v]++; } queue<int> Q; for(int i = 1; i <= n; ++i) if(!deg[i]) Q.emplace(i); while(!Q.empty()) { int u = Q.front(); Q.pop(); topo.emplace_back(u); for(auto x : tod[u]) block[u].emplace_back(x); block[u].emplace_back(u, 0); sort(all(block[u]), [&](const pii &a, const pii &b) { return a.y > b.y; }); if(block[u].size() > sz) block[u].resize(sz); for(int v : g[u]) { for(pii x : block[u]) tod[v][x.x] = max(tod[v][x.x], x.y + 1); if(!--deg[v]) Q.emplace(v); } } for(int i = 0, u, t; i < q; ++i) { scanf("%d %d", &u, &t); vector<int> vec; for(int i = 0, v; i < t; ++i) scanf("%d", &v), vec.emplace_back(v); if(t < sz) { for(int v : vec) mark[v] ^= 1; bool st = true; for(pii v : block[u]) if(!mark[v.x]) { printf("%d\n", v.y), st = false; break; } if(st) puts("-1"); for(int v : vec) mark[v] ^= 1; } else { memset(d, 0, sizeof d); for(int v : vec) d[v] = -INF; for(int i = 0; i < n; ++i) { int u = topo[i]; for(int v : g[u]) d[v] = max(d[v], d[u] + 1); } printf("%d\n", d[u] < 0 ? -1 : d[u]); } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 9720 KB | Output is correct |
2 | Correct | 13 ms | 9844 KB | Output is correct |
3 | Correct | 12 ms | 9844 KB | Output is correct |
4 | Correct | 11 ms | 9956 KB | Output is correct |
5 | Correct | 26 ms | 12432 KB | Output is correct |
6 | Correct | 26 ms | 12576 KB | Output is correct |
7 | Correct | 29 ms | 12576 KB | Output is correct |
8 | Correct | 109 ms | 27312 KB | Output is correct |
9 | Correct | 107 ms | 27312 KB | Output is correct |
10 | Correct | 99 ms | 27312 KB | Output is correct |
11 | Correct | 113 ms | 27312 KB | Output is correct |
12 | Correct | 58 ms | 27312 KB | Output is correct |
13 | Correct | 108 ms | 27312 KB | Output is correct |
14 | Correct | 88 ms | 27312 KB | Output is correct |
15 | Correct | 57 ms | 27312 KB | Output is correct |
16 | Correct | 86 ms | 27312 KB | Output is correct |
17 | Correct | 88 ms | 27312 KB | Output is correct |
18 | Correct | 65 ms | 27312 KB | Output is correct |
19 | Correct | 82 ms | 27312 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 9720 KB | Output is correct |
2 | Correct | 13 ms | 9844 KB | Output is correct |
3 | Correct | 12 ms | 9844 KB | Output is correct |
4 | Correct | 11 ms | 9956 KB | Output is correct |
5 | Correct | 26 ms | 12432 KB | Output is correct |
6 | Correct | 26 ms | 12576 KB | Output is correct |
7 | Correct | 29 ms | 12576 KB | Output is correct |
8 | Correct | 109 ms | 27312 KB | Output is correct |
9 | Correct | 107 ms | 27312 KB | Output is correct |
10 | Correct | 99 ms | 27312 KB | Output is correct |
11 | Correct | 113 ms | 27312 KB | Output is correct |
12 | Correct | 58 ms | 27312 KB | Output is correct |
13 | Correct | 108 ms | 27312 KB | Output is correct |
14 | Correct | 88 ms | 27312 KB | Output is correct |
15 | Correct | 57 ms | 27312 KB | Output is correct |
16 | Correct | 86 ms | 27312 KB | Output is correct |
17 | Correct | 88 ms | 27312 KB | Output is correct |
18 | Correct | 65 ms | 27312 KB | Output is correct |
19 | Correct | 82 ms | 27312 KB | Output is correct |
20 | Execution timed out | 2060 ms | 27312 KB | Time limit exceeded |
21 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 9720 KB | Output is correct |
2 | Correct | 13 ms | 9844 KB | Output is correct |
3 | Correct | 12 ms | 9844 KB | Output is correct |
4 | Correct | 11 ms | 9956 KB | Output is correct |
5 | Correct | 26 ms | 12432 KB | Output is correct |
6 | Correct | 26 ms | 12576 KB | Output is correct |
7 | Correct | 29 ms | 12576 KB | Output is correct |
8 | Correct | 109 ms | 27312 KB | Output is correct |
9 | Correct | 107 ms | 27312 KB | Output is correct |
10 | Correct | 99 ms | 27312 KB | Output is correct |
11 | Correct | 113 ms | 27312 KB | Output is correct |
12 | Correct | 58 ms | 27312 KB | Output is correct |
13 | Correct | 108 ms | 27312 KB | Output is correct |
14 | Correct | 88 ms | 27312 KB | Output is correct |
15 | Correct | 57 ms | 27312 KB | Output is correct |
16 | Correct | 86 ms | 27312 KB | Output is correct |
17 | Correct | 88 ms | 27312 KB | Output is correct |
18 | Correct | 65 ms | 27312 KB | Output is correct |
19 | Correct | 82 ms | 27312 KB | Output is correct |
20 | Execution timed out | 2060 ms | 27312 KB | Time limit exceeded |
21 | Halted | 0 ms | 0 KB | - |