# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
83866 | 2018-11-11T13:07:02 Z | win11905 | Bitaro’s Party (JOI18_bitaro) | C++11 | 25 ms | 12736 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 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] = -1; 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]); } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 9720 KB | Output is correct |
2 | Correct | 10 ms | 9852 KB | Output is correct |
3 | Correct | 10 ms | 9852 KB | Output is correct |
4 | Correct | 11 ms | 9852 KB | Output is correct |
5 | Correct | 25 ms | 12408 KB | Output is correct |
6 | Correct | 19 ms | 12736 KB | Output is correct |
7 | Incorrect | 23 ms | 12736 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 9720 KB | Output is correct |
2 | Correct | 10 ms | 9852 KB | Output is correct |
3 | Correct | 10 ms | 9852 KB | Output is correct |
4 | Correct | 11 ms | 9852 KB | Output is correct |
5 | Correct | 25 ms | 12408 KB | Output is correct |
6 | Correct | 19 ms | 12736 KB | Output is correct |
7 | Incorrect | 23 ms | 12736 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 9720 KB | Output is correct |
2 | Correct | 10 ms | 9852 KB | Output is correct |
3 | Correct | 10 ms | 9852 KB | Output is correct |
4 | Correct | 11 ms | 9852 KB | Output is correct |
5 | Correct | 25 ms | 12408 KB | Output is correct |
6 | Correct | 19 ms | 12736 KB | Output is correct |
7 | Incorrect | 23 ms | 12736 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |