# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
56694 | 2018-07-12T07:58:12 Z | khsoo01 | Bitaro’s Party (JOI18_bitaro) | C++11 | 1820 ms | 211152 KB |
#include<bits/stdc++.h> #define X first #define Y second using namespace std; typedef pair<int,int> pii; const int N = 100005, X = 255, inf = 1e9; int n, m, q, o, k, b[N], opt[N]; bool vis[N]; vector<int> adj[N], usd; vector<pii> dt[N]; void upd (vector<pii> &V, const pii &T) { V.push_back(T); vis[T.Y] = true; usd.push_back(T.Y); } int main() { scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=m;i++) { int A, B; scanf("%d%d",&A,&B); adj[B].push_back(A); } for(int i=1;i<=n;i++) { for(auto &T : adj[i]) { vector<pii> D; int P = dt[i].size(), Q = dt[T].size(); for(int A=0, B=0; (A<P || B<Q) && D.size()<X; ) { if(A != P && vis[dt[i][A].Y]) A++; else if(B != Q && vis[dt[T][B].Y]) B++; else if(A == P) upd(D, pii(dt[T][B].X+1, dt[T][B].Y)); else if(B == Q) upd(D, dt[i][A]); else upd(D, max(pii(dt[T][B].X+1, dt[T][B].Y), dt[i][A])); } swap(D, dt[i]); for(auto &T : usd) { vis[T] = false; } usd.clear(); } if(dt[i].size() < X) dt[i].push_back({0, i}); } while(q--) { scanf("%d%d",&o,&k); for(int i=1;i<=k;i++) { scanf("%d",&b[i]); vis[b[i]] = true; } if(dt[o].size() < X || k < X) { bool F = false; for(auto &T : dt[o]) { if(vis[T.Y]) continue; printf("%d\n",T.X); F = true; break; } if(!F) puts("-1"); } else { for(int i=1;i<=o;i++) { opt[i] = (vis[i] ? -inf : 0); for(auto &T : adj[i]) { opt[i] = max(opt[i], opt[T] + 1); } } printf("%d\n",(opt[o] < 0 ? -1 : opt[o])); } for(int i=1;i<=k;i++) { vis[b[i]] = false; } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 5108 KB | Output is correct |
3 | Correct | 7 ms | 5172 KB | Output is correct |
4 | Correct | 7 ms | 5220 KB | Output is correct |
5 | Correct | 11 ms | 5664 KB | Output is correct |
6 | Correct | 10 ms | 5704 KB | Output is correct |
7 | Correct | 11 ms | 5712 KB | Output is correct |
8 | Correct | 18 ms | 7120 KB | Output is correct |
9 | Correct | 20 ms | 7120 KB | Output is correct |
10 | Correct | 20 ms | 7120 KB | Output is correct |
11 | Correct | 18 ms | 7120 KB | Output is correct |
12 | Correct | 15 ms | 7120 KB | Output is correct |
13 | Correct | 18 ms | 7120 KB | Output is correct |
14 | Correct | 17 ms | 7120 KB | Output is correct |
15 | Correct | 15 ms | 7120 KB | Output is correct |
16 | Correct | 16 ms | 7120 KB | Output is correct |
17 | Correct | 19 ms | 7120 KB | Output is correct |
18 | Correct | 16 ms | 7120 KB | Output is correct |
19 | Correct | 18 ms | 7120 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 5108 KB | Output is correct |
3 | Correct | 7 ms | 5172 KB | Output is correct |
4 | Correct | 7 ms | 5220 KB | Output is correct |
5 | Correct | 11 ms | 5664 KB | Output is correct |
6 | Correct | 10 ms | 5704 KB | Output is correct |
7 | Correct | 11 ms | 5712 KB | Output is correct |
8 | Correct | 18 ms | 7120 KB | Output is correct |
9 | Correct | 20 ms | 7120 KB | Output is correct |
10 | Correct | 20 ms | 7120 KB | Output is correct |
11 | Correct | 18 ms | 7120 KB | Output is correct |
12 | Correct | 15 ms | 7120 KB | Output is correct |
13 | Correct | 18 ms | 7120 KB | Output is correct |
14 | Correct | 17 ms | 7120 KB | Output is correct |
15 | Correct | 15 ms | 7120 KB | Output is correct |
16 | Correct | 16 ms | 7120 KB | Output is correct |
17 | Correct | 19 ms | 7120 KB | Output is correct |
18 | Correct | 16 ms | 7120 KB | Output is correct |
19 | Correct | 18 ms | 7120 KB | Output is correct |
20 | Correct | 1083 ms | 8428 KB | Output is correct |
21 | Correct | 1096 ms | 8428 KB | Output is correct |
22 | Correct | 1036 ms | 8428 KB | Output is correct |
23 | Correct | 1078 ms | 8428 KB | Output is correct |
24 | Correct | 1528 ms | 150964 KB | Output is correct |
25 | Correct | 1598 ms | 155404 KB | Output is correct |
26 | Correct | 1604 ms | 155504 KB | Output is correct |
27 | Correct | 1705 ms | 210824 KB | Output is correct |
28 | Correct | 1603 ms | 211060 KB | Output is correct |
29 | Correct | 1664 ms | 211060 KB | Output is correct |
30 | Correct | 1656 ms | 211060 KB | Output is correct |
31 | Correct | 1651 ms | 211060 KB | Output is correct |
32 | Correct | 1575 ms | 211060 KB | Output is correct |
33 | Correct | 1196 ms | 211060 KB | Output is correct |
34 | Correct | 1061 ms | 211060 KB | Output is correct |
35 | Correct | 1154 ms | 211060 KB | Output is correct |
36 | Correct | 1372 ms | 211060 KB | Output is correct |
37 | Correct | 1381 ms | 211060 KB | Output is correct |
38 | Correct | 1380 ms | 211060 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 5108 KB | Output is correct |
3 | Correct | 7 ms | 5172 KB | Output is correct |
4 | Correct | 7 ms | 5220 KB | Output is correct |
5 | Correct | 11 ms | 5664 KB | Output is correct |
6 | Correct | 10 ms | 5704 KB | Output is correct |
7 | Correct | 11 ms | 5712 KB | Output is correct |
8 | Correct | 18 ms | 7120 KB | Output is correct |
9 | Correct | 20 ms | 7120 KB | Output is correct |
10 | Correct | 20 ms | 7120 KB | Output is correct |
11 | Correct | 18 ms | 7120 KB | Output is correct |
12 | Correct | 15 ms | 7120 KB | Output is correct |
13 | Correct | 18 ms | 7120 KB | Output is correct |
14 | Correct | 17 ms | 7120 KB | Output is correct |
15 | Correct | 15 ms | 7120 KB | Output is correct |
16 | Correct | 16 ms | 7120 KB | Output is correct |
17 | Correct | 19 ms | 7120 KB | Output is correct |
18 | Correct | 16 ms | 7120 KB | Output is correct |
19 | Correct | 18 ms | 7120 KB | Output is correct |
20 | Correct | 1083 ms | 8428 KB | Output is correct |
21 | Correct | 1096 ms | 8428 KB | Output is correct |
22 | Correct | 1036 ms | 8428 KB | Output is correct |
23 | Correct | 1078 ms | 8428 KB | Output is correct |
24 | Correct | 1528 ms | 150964 KB | Output is correct |
25 | Correct | 1598 ms | 155404 KB | Output is correct |
26 | Correct | 1604 ms | 155504 KB | Output is correct |
27 | Correct | 1705 ms | 210824 KB | Output is correct |
28 | Correct | 1603 ms | 211060 KB | Output is correct |
29 | Correct | 1664 ms | 211060 KB | Output is correct |
30 | Correct | 1656 ms | 211060 KB | Output is correct |
31 | Correct | 1651 ms | 211060 KB | Output is correct |
32 | Correct | 1575 ms | 211060 KB | Output is correct |
33 | Correct | 1196 ms | 211060 KB | Output is correct |
34 | Correct | 1061 ms | 211060 KB | Output is correct |
35 | Correct | 1154 ms | 211060 KB | Output is correct |
36 | Correct | 1372 ms | 211060 KB | Output is correct |
37 | Correct | 1381 ms | 211060 KB | Output is correct |
38 | Correct | 1380 ms | 211060 KB | Output is correct |
39 | Correct | 1482 ms | 211060 KB | Output is correct |
40 | Correct | 1508 ms | 211060 KB | Output is correct |
41 | Correct | 1535 ms | 211060 KB | Output is correct |
42 | Correct | 1593 ms | 211060 KB | Output is correct |
43 | Correct | 1502 ms | 211060 KB | Output is correct |
44 | Correct | 1074 ms | 211060 KB | Output is correct |
45 | Correct | 1044 ms | 211060 KB | Output is correct |
46 | Correct | 1051 ms | 211060 KB | Output is correct |
47 | Correct | 1043 ms | 211060 KB | Output is correct |
48 | Correct | 1045 ms | 211060 KB | Output is correct |
49 | Correct | 1584 ms | 211084 KB | Output is correct |
50 | Correct | 1580 ms | 211084 KB | Output is correct |
51 | Correct | 1094 ms | 211084 KB | Output is correct |
52 | Correct | 1058 ms | 211084 KB | Output is correct |
53 | Correct | 1545 ms | 211084 KB | Output is correct |
54 | Correct | 1439 ms | 211084 KB | Output is correct |
55 | Correct | 1409 ms | 211084 KB | Output is correct |
56 | Correct | 1340 ms | 211084 KB | Output is correct |
57 | Correct | 1076 ms | 211084 KB | Output is correct |
58 | Correct | 1088 ms | 211084 KB | Output is correct |
59 | Correct | 1061 ms | 211084 KB | Output is correct |
60 | Correct | 1042 ms | 211084 KB | Output is correct |
61 | Correct | 1582 ms | 211084 KB | Output is correct |
62 | Correct | 1508 ms | 211084 KB | Output is correct |
63 | Correct | 1426 ms | 211084 KB | Output is correct |
64 | Correct | 1820 ms | 211084 KB | Output is correct |
65 | Correct | 1614 ms | 211084 KB | Output is correct |
66 | Correct | 1591 ms | 211084 KB | Output is correct |
67 | Correct | 1630 ms | 211084 KB | Output is correct |
68 | Correct | 1388 ms | 211084 KB | Output is correct |
69 | Correct | 1429 ms | 211084 KB | Output is correct |
70 | Correct | 1546 ms | 211084 KB | Output is correct |
71 | Correct | 1357 ms | 211084 KB | Output is correct |
72 | Correct | 1384 ms | 211084 KB | Output is correct |
73 | Correct | 1565 ms | 211084 KB | Output is correct |
74 | Correct | 1429 ms | 211084 KB | Output is correct |
75 | Correct | 1494 ms | 211084 KB | Output is correct |
76 | Correct | 1606 ms | 211116 KB | Output is correct |
77 | Correct | 1511 ms | 211116 KB | Output is correct |
78 | Correct | 1521 ms | 211152 KB | Output is correct |
79 | Correct | 1098 ms | 211152 KB | Output is correct |
80 | Correct | 1067 ms | 211152 KB | Output is correct |
81 | Correct | 1061 ms | 211152 KB | Output is correct |
82 | Correct | 1646 ms | 211152 KB | Output is correct |
83 | Correct | 1786 ms | 211152 KB | Output is correct |
84 | Correct | 1575 ms | 211152 KB | Output is correct |
85 | Correct | 1602 ms | 211152 KB | Output is correct |
86 | Correct | 1476 ms | 211152 KB | Output is correct |
87 | Correct | 1595 ms | 211152 KB | Output is correct |
88 | Correct | 1083 ms | 211152 KB | Output is correct |
89 | Correct | 1109 ms | 211152 KB | Output is correct |
90 | Correct | 1051 ms | 211152 KB | Output is correct |
91 | Correct | 1051 ms | 211152 KB | Output is correct |
92 | Correct | 1039 ms | 211152 KB | Output is correct |
93 | Correct | 1026 ms | 211152 KB | Output is correct |
94 | Correct | 1263 ms | 211152 KB | Output is correct |
95 | Correct | 1206 ms | 211152 KB | Output is correct |
96 | Correct | 1184 ms | 211152 KB | Output is correct |
97 | Correct | 1070 ms | 211152 KB | Output is correct |
98 | Correct | 1180 ms | 211152 KB | Output is correct |
99 | Correct | 1175 ms | 211152 KB | Output is correct |
100 | Correct | 1120 ms | 211152 KB | Output is correct |
101 | Correct | 1136 ms | 211152 KB | Output is correct |
102 | Correct | 1103 ms | 211152 KB | Output is correct |
103 | Correct | 1095 ms | 211152 KB | Output is correct |
104 | Correct | 1090 ms | 211152 KB | Output is correct |
105 | Correct | 1096 ms | 211152 KB | Output is correct |
106 | Correct | 1444 ms | 211152 KB | Output is correct |
107 | Correct | 1492 ms | 211152 KB | Output is correct |
108 | Correct | 1380 ms | 211152 KB | Output is correct |
109 | Correct | 1357 ms | 211152 KB | Output is correct |
110 | Correct | 1350 ms | 211152 KB | Output is correct |
111 | Correct | 1427 ms | 211152 KB | Output is correct |
112 | Correct | 1109 ms | 211152 KB | Output is correct |
113 | Correct | 1090 ms | 211152 KB | Output is correct |
114 | Correct | 1044 ms | 211152 KB | Output is correct |
115 | Correct | 1032 ms | 211152 KB | Output is correct |
116 | Correct | 1076 ms | 211152 KB | Output is correct |
117 | Correct | 1044 ms | 211152 KB | Output is correct |
118 | Correct | 1516 ms | 211152 KB | Output is correct |
119 | Correct | 1406 ms | 211152 KB | Output is correct |
120 | Correct | 1370 ms | 211152 KB | Output is correct |
121 | Correct | 1568 ms | 211152 KB | Output is correct |
122 | Correct | 1451 ms | 211152 KB | Output is correct |
123 | Correct | 1411 ms | 211152 KB | Output is correct |
124 | Correct | 1571 ms | 211152 KB | Output is correct |
125 | Correct | 1436 ms | 211152 KB | Output is correct |
126 | Correct | 1423 ms | 211152 KB | Output is correct |