# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
87756 | 2018-12-02T10:13:34 Z | win11905 | Bitaro’s Party (JOI18_bitaro) | C++11 | 2000 ms | 17068 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 = 100; 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 9748 KB | Output is correct |
2 | Correct | 10 ms | 9748 KB | Output is correct |
3 | Correct | 10 ms | 9804 KB | Output is correct |
4 | Correct | 10 ms | 9848 KB | Output is correct |
5 | Correct | 24 ms | 12408 KB | Output is correct |
6 | Correct | 24 ms | 12552 KB | Output is correct |
7 | Correct | 23 ms | 12552 KB | Output is correct |
8 | Correct | 32 ms | 15780 KB | Output is correct |
9 | Correct | 31 ms | 15820 KB | Output is correct |
10 | Correct | 33 ms | 15820 KB | Output is correct |
11 | Correct | 40 ms | 15820 KB | Output is correct |
12 | Correct | 36 ms | 15820 KB | Output is correct |
13 | Correct | 40 ms | 15820 KB | Output is correct |
14 | Correct | 35 ms | 15820 KB | Output is correct |
15 | Correct | 30 ms | 15820 KB | Output is correct |
16 | Correct | 34 ms | 15820 KB | Output is correct |
17 | Correct | 37 ms | 15820 KB | Output is correct |
18 | Correct | 36 ms | 15820 KB | Output is correct |
19 | Correct | 45 ms | 15820 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 9748 KB | Output is correct |
2 | Correct | 10 ms | 9748 KB | Output is correct |
3 | Correct | 10 ms | 9804 KB | Output is correct |
4 | Correct | 10 ms | 9848 KB | Output is correct |
5 | Correct | 24 ms | 12408 KB | Output is correct |
6 | Correct | 24 ms | 12552 KB | Output is correct |
7 | Correct | 23 ms | 12552 KB | Output is correct |
8 | Correct | 32 ms | 15780 KB | Output is correct |
9 | Correct | 31 ms | 15820 KB | Output is correct |
10 | Correct | 33 ms | 15820 KB | Output is correct |
11 | Correct | 40 ms | 15820 KB | Output is correct |
12 | Correct | 36 ms | 15820 KB | Output is correct |
13 | Correct | 40 ms | 15820 KB | Output is correct |
14 | Correct | 35 ms | 15820 KB | Output is correct |
15 | Correct | 30 ms | 15820 KB | Output is correct |
16 | Correct | 34 ms | 15820 KB | Output is correct |
17 | Correct | 37 ms | 15820 KB | Output is correct |
18 | Correct | 36 ms | 15820 KB | Output is correct |
19 | Correct | 45 ms | 15820 KB | Output is correct |
20 | Correct | 780 ms | 16864 KB | Output is correct |
21 | Correct | 722 ms | 17068 KB | Output is correct |
22 | Correct | 847 ms | 17068 KB | Output is correct |
23 | Execution timed out | 2041 ms | 17068 KB | Time limit exceeded |
24 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 9748 KB | Output is correct |
2 | Correct | 10 ms | 9748 KB | Output is correct |
3 | Correct | 10 ms | 9804 KB | Output is correct |
4 | Correct | 10 ms | 9848 KB | Output is correct |
5 | Correct | 24 ms | 12408 KB | Output is correct |
6 | Correct | 24 ms | 12552 KB | Output is correct |
7 | Correct | 23 ms | 12552 KB | Output is correct |
8 | Correct | 32 ms | 15780 KB | Output is correct |
9 | Correct | 31 ms | 15820 KB | Output is correct |
10 | Correct | 33 ms | 15820 KB | Output is correct |
11 | Correct | 40 ms | 15820 KB | Output is correct |
12 | Correct | 36 ms | 15820 KB | Output is correct |
13 | Correct | 40 ms | 15820 KB | Output is correct |
14 | Correct | 35 ms | 15820 KB | Output is correct |
15 | Correct | 30 ms | 15820 KB | Output is correct |
16 | Correct | 34 ms | 15820 KB | Output is correct |
17 | Correct | 37 ms | 15820 KB | Output is correct |
18 | Correct | 36 ms | 15820 KB | Output is correct |
19 | Correct | 45 ms | 15820 KB | Output is correct |
20 | Correct | 780 ms | 16864 KB | Output is correct |
21 | Correct | 722 ms | 17068 KB | Output is correct |
22 | Correct | 847 ms | 17068 KB | Output is correct |
23 | Execution timed out | 2041 ms | 17068 KB | Time limit exceeded |
24 | Halted | 0 ms | 0 KB | - |