# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
95472 | 2019-02-01T13:23:58 Z | Retro3014 | Bitaro’s Party (JOI18_bitaro) | C++17 | 1713 ms | 420948 KB |
#include <iostream> #include <algorithm> #include <stdio.h> #include <vector> #include <math.h> #include <queue> using namespace std; #define MAX_N 100000 int N, M, Q; int Y, SQ; vector<int> gp[MAX_N+1]; vector<pair<int, int> > edge; struct S{ S (int idx, int data) : idx(idx), data(data) {} int idx, data; bool operator <(const S &a)const{ if(data==a.data){ return idx<a.idx; } return data<a.data; } }; vector<S> vt[MAX_N+1]; struct QUERY{ int t, y; vector<int> c; }; vector<QUERY> Query; bool chk[MAX_N+1]; int dist[MAX_N+1]; void solve_query(QUERY now){ for(int i=0; i<now.y; i++){ chk[now.c[i]] = true; } if(now.y>=SQ){ int ans = -1; for(int i = now.t; i>=1; i--){ if(i!=now.t && dist[i]==0){ continue; } if(!chk[i]){ ans = max(ans, dist[i]); } for(int j=0; j<gp[i].size(); j++){ dist[gp[i][j]] = max(dist[gp[i][j]], dist[i]+1); } dist[i] = 0; } printf("%d\n", ans); }else{ int idx = 0; while(idx<vt[now.t].size()){ if(chk[vt[now.t][idx].idx]) idx++; else break; } if(idx==vt[now.t].size()) printf("-1\n"); else printf("%d\n", vt[now.t][idx].data); } for(int i=0; i<now.y; i++){ chk[now.c[i]] = false; } } priority_queue<S> pq; vector<S> tmpv; void solve(){ SQ = sqrt(Y); for(int i=1; i<=N; i++){ vt[i].push_back({i, 0}); } for(int i=0; i<edge.size(); i++){ pair<int, int> p = edge[i]; while(!tmpv.empty()) tmpv.pop_back(); for(int j=0; j<vt[p.second].size(); j++){ tmpv.push_back(vt[p.second][j]); } while(!vt[p.second].empty()) vt[p.second].pop_back(); int idx1 = 0, idx2 = 0; while((idx1<vt[p.first].size() || idx2<tmpv.size()) && vt[p.second].size()<SQ){ if(idx1==vt[p.first].size()){ if(!chk[tmpv[idx2].idx]){ vt[p.second].push_back(tmpv[idx2]); chk[tmpv[idx2].idx] = true; } idx2++; }else if(idx2==tmpv.size()){ if(!chk[vt[p.first][idx1].idx]){ vt[p.second].push_back({vt[p.first][idx1].idx, vt[p.first][idx1].data+1}); chk[vt[p.first][idx1].idx] = true; } idx1++; }else{ if(vt[p.first][idx1].data+1>=tmpv[idx2].data){ if(!chk[vt[p.first][idx1].idx]){ vt[p.second].push_back({vt[p.first][idx1].idx, vt[p.first][idx1].data+1}); chk[vt[p.first][idx1].idx] = true; } idx1++; }else{ if(!chk[tmpv[idx2].idx]){ vt[p.second].push_back(tmpv[idx2]); chk[tmpv[idx2].idx] = true; } idx2++; } } } for(int j=0; j<vt[p.second].size(); j++){ chk[vt[p.second][j].idx] = false; } } } int main(){ scanf("%d%d%d", &N, &M, &Q); for(int i=0; i<M; i++){ int a, b; scanf("%d%d", &a, &b); gp[b].push_back(a); edge.push_back(make_pair(a, b)); } sort(edge.begin(), edge.end()); for(int i=0; i<Q; i++){ QUERY tmp; scanf("%d%d", &tmp.t, &tmp.y); Y+=tmp.y; while(!tmp.c.empty()) tmp.c.pop_back(); for(int i=0; i<tmp.y; i++){ int x; scanf("%d", &x); tmp.c.push_back(x); } Query.push_back(tmp); } //cout<<1<<endl; solve(); for(int i=0; i<Query.size(); i++){ solve_query(Query[i]); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 4984 KB | Output is correct |
2 | Correct | 5 ms | 4984 KB | Output is correct |
3 | Correct | 5 ms | 4984 KB | Output is correct |
4 | Correct | 6 ms | 4984 KB | Output is correct |
5 | Correct | 7 ms | 5368 KB | Output is correct |
6 | Correct | 7 ms | 5240 KB | Output is correct |
7 | Correct | 7 ms | 5368 KB | Output is correct |
8 | Correct | 7 ms | 5368 KB | Output is correct |
9 | Correct | 8 ms | 5372 KB | Output is correct |
10 | Correct | 7 ms | 5368 KB | Output is correct |
11 | Correct | 7 ms | 5368 KB | Output is correct |
12 | Correct | 7 ms | 5368 KB | Output is correct |
13 | Correct | 8 ms | 5240 KB | Output is correct |
14 | Correct | 6 ms | 5240 KB | Output is correct |
15 | Correct | 6 ms | 5240 KB | Output is correct |
16 | Correct | 6 ms | 5240 KB | Output is correct |
17 | Correct | 7 ms | 5240 KB | Output is correct |
18 | Correct | 6 ms | 5244 KB | Output is correct |
19 | Correct | 7 ms | 5240 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 4984 KB | Output is correct |
2 | Correct | 5 ms | 4984 KB | Output is correct |
3 | Correct | 5 ms | 4984 KB | Output is correct |
4 | Correct | 6 ms | 4984 KB | Output is correct |
5 | Correct | 7 ms | 5368 KB | Output is correct |
6 | Correct | 7 ms | 5240 KB | Output is correct |
7 | Correct | 7 ms | 5368 KB | Output is correct |
8 | Correct | 7 ms | 5368 KB | Output is correct |
9 | Correct | 8 ms | 5372 KB | Output is correct |
10 | Correct | 7 ms | 5368 KB | Output is correct |
11 | Correct | 7 ms | 5368 KB | Output is correct |
12 | Correct | 7 ms | 5368 KB | Output is correct |
13 | Correct | 8 ms | 5240 KB | Output is correct |
14 | Correct | 6 ms | 5240 KB | Output is correct |
15 | Correct | 6 ms | 5240 KB | Output is correct |
16 | Correct | 6 ms | 5240 KB | Output is correct |
17 | Correct | 7 ms | 5240 KB | Output is correct |
18 | Correct | 6 ms | 5244 KB | Output is correct |
19 | Correct | 7 ms | 5240 KB | Output is correct |
20 | Correct | 136 ms | 8012 KB | Output is correct |
21 | Correct | 144 ms | 8052 KB | Output is correct |
22 | Correct | 146 ms | 8040 KB | Output is correct |
23 | Correct | 140 ms | 8056 KB | Output is correct |
24 | Correct | 992 ms | 156428 KB | Output is correct |
25 | Correct | 865 ms | 161904 KB | Output is correct |
26 | Correct | 811 ms | 162284 KB | Output is correct |
27 | Correct | 1028 ms | 212520 KB | Output is correct |
28 | Correct | 1092 ms | 214980 KB | Output is correct |
29 | Correct | 1081 ms | 214932 KB | Output is correct |
30 | Correct | 1075 ms | 214552 KB | Output is correct |
31 | Correct | 1058 ms | 211556 KB | Output is correct |
32 | Correct | 1052 ms | 214556 KB | Output is correct |
33 | Correct | 747 ms | 138980 KB | Output is correct |
34 | Correct | 699 ms | 121116 KB | Output is correct |
35 | Correct | 778 ms | 137956 KB | Output is correct |
36 | Correct | 912 ms | 178332 KB | Output is correct |
37 | Correct | 869 ms | 167040 KB | Output is correct |
38 | Correct | 956 ms | 178804 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 4984 KB | Output is correct |
2 | Correct | 5 ms | 4984 KB | Output is correct |
3 | Correct | 5 ms | 4984 KB | Output is correct |
4 | Correct | 6 ms | 4984 KB | Output is correct |
5 | Correct | 7 ms | 5368 KB | Output is correct |
6 | Correct | 7 ms | 5240 KB | Output is correct |
7 | Correct | 7 ms | 5368 KB | Output is correct |
8 | Correct | 7 ms | 5368 KB | Output is correct |
9 | Correct | 8 ms | 5372 KB | Output is correct |
10 | Correct | 7 ms | 5368 KB | Output is correct |
11 | Correct | 7 ms | 5368 KB | Output is correct |
12 | Correct | 7 ms | 5368 KB | Output is correct |
13 | Correct | 8 ms | 5240 KB | Output is correct |
14 | Correct | 6 ms | 5240 KB | Output is correct |
15 | Correct | 6 ms | 5240 KB | Output is correct |
16 | Correct | 6 ms | 5240 KB | Output is correct |
17 | Correct | 7 ms | 5240 KB | Output is correct |
18 | Correct | 6 ms | 5244 KB | Output is correct |
19 | Correct | 7 ms | 5240 KB | Output is correct |
20 | Correct | 136 ms | 8012 KB | Output is correct |
21 | Correct | 144 ms | 8052 KB | Output is correct |
22 | Correct | 146 ms | 8040 KB | Output is correct |
23 | Correct | 140 ms | 8056 KB | Output is correct |
24 | Correct | 992 ms | 156428 KB | Output is correct |
25 | Correct | 865 ms | 161904 KB | Output is correct |
26 | Correct | 811 ms | 162284 KB | Output is correct |
27 | Correct | 1028 ms | 212520 KB | Output is correct |
28 | Correct | 1092 ms | 214980 KB | Output is correct |
29 | Correct | 1081 ms | 214932 KB | Output is correct |
30 | Correct | 1075 ms | 214552 KB | Output is correct |
31 | Correct | 1058 ms | 211556 KB | Output is correct |
32 | Correct | 1052 ms | 214556 KB | Output is correct |
33 | Correct | 747 ms | 138980 KB | Output is correct |
34 | Correct | 699 ms | 121116 KB | Output is correct |
35 | Correct | 778 ms | 137956 KB | Output is correct |
36 | Correct | 912 ms | 178332 KB | Output is correct |
37 | Correct | 869 ms | 167040 KB | Output is correct |
38 | Correct | 956 ms | 178804 KB | Output is correct |
39 | Correct | 1211 ms | 270652 KB | Output is correct |
40 | Correct | 1098 ms | 267332 KB | Output is correct |
41 | Correct | 1101 ms | 270056 KB | Output is correct |
42 | Correct | 1081 ms | 268296 KB | Output is correct |
43 | Correct | 1166 ms | 267528 KB | Output is correct |
44 | Correct | 832 ms | 19228 KB | Output is correct |
45 | Correct | 799 ms | 14100 KB | Output is correct |
46 | Correct | 802 ms | 13800 KB | Output is correct |
47 | Correct | 632 ms | 11620 KB | Output is correct |
48 | Correct | 284 ms | 10284 KB | Output is correct |
49 | Correct | 1435 ms | 420844 KB | Output is correct |
50 | Correct | 1475 ms | 414972 KB | Output is correct |
51 | Correct | 843 ms | 19204 KB | Output is correct |
52 | Correct | 789 ms | 13672 KB | Output is correct |
53 | Correct | 1248 ms | 343012 KB | Output is correct |
54 | Correct | 1187 ms | 314576 KB | Output is correct |
55 | Correct | 1164 ms | 337540 KB | Output is correct |
56 | Correct | 1126 ms | 309828 KB | Output is correct |
57 | Correct | 813 ms | 19140 KB | Output is correct |
58 | Correct | 864 ms | 19064 KB | Output is correct |
59 | Correct | 790 ms | 13608 KB | Output is correct |
60 | Correct | 795 ms | 13576 KB | Output is correct |
61 | Correct | 1609 ms | 415508 KB | Output is correct |
62 | Correct | 1320 ms | 339440 KB | Output is correct |
63 | Correct | 1234 ms | 308388 KB | Output is correct |
64 | Correct | 1713 ms | 415304 KB | Output is correct |
65 | Correct | 1395 ms | 337892 KB | Output is correct |
66 | Correct | 1194 ms | 310364 KB | Output is correct |
67 | Correct | 1425 ms | 414984 KB | Output is correct |
68 | Correct | 1128 ms | 338988 KB | Output is correct |
69 | Correct | 1130 ms | 305892 KB | Output is correct |
70 | Correct | 1456 ms | 415592 KB | Output is correct |
71 | Correct | 1310 ms | 339444 KB | Output is correct |
72 | Correct | 1191 ms | 309604 KB | Output is correct |
73 | Correct | 1585 ms | 415656 KB | Output is correct |
74 | Correct | 1264 ms | 339336 KB | Output is correct |
75 | Correct | 1055 ms | 309680 KB | Output is correct |
76 | Correct | 1449 ms | 420948 KB | Output is correct |
77 | Correct | 1416 ms | 415204 KB | Output is correct |
78 | Correct | 1365 ms | 415652 KB | Output is correct |
79 | Correct | 811 ms | 19040 KB | Output is correct |
80 | Correct | 776 ms | 13540 KB | Output is correct |
81 | Correct | 280 ms | 10296 KB | Output is correct |
82 | Correct | 1527 ms | 420724 KB | Output is correct |
83 | Correct | 1369 ms | 409836 KB | Output is correct |
84 | Correct | 1334 ms | 414948 KB | Output is correct |
85 | Correct | 1336 ms | 403812 KB | Output is correct |
86 | Correct | 1400 ms | 415240 KB | Output is correct |
87 | Correct | 1531 ms | 405032 KB | Output is correct |
88 | Correct | 827 ms | 19044 KB | Output is correct |
89 | Correct | 839 ms | 19136 KB | Output is correct |
90 | Correct | 781 ms | 13708 KB | Output is correct |
91 | Correct | 794 ms | 13596 KB | Output is correct |
92 | Correct | 302 ms | 10340 KB | Output is correct |
93 | Correct | 285 ms | 10444 KB | Output is correct |
94 | Correct | 1099 ms | 265184 KB | Output is correct |
95 | Correct | 949 ms | 219348 KB | Output is correct |
96 | Correct | 922 ms | 258012 KB | Output is correct |
97 | Correct | 887 ms | 217676 KB | Output is correct |
98 | Correct | 1018 ms | 259388 KB | Output is correct |
99 | Correct | 951 ms | 217272 KB | Output is correct |
100 | Correct | 1014 ms | 19108 KB | Output is correct |
101 | Correct | 974 ms | 19100 KB | Output is correct |
102 | Correct | 930 ms | 13796 KB | Output is correct |
103 | Correct | 952 ms | 13796 KB | Output is correct |
104 | Correct | 290 ms | 10340 KB | Output is correct |
105 | Correct | 296 ms | 10468 KB | Output is correct |
106 | Correct | 1383 ms | 343464 KB | Output is correct |
107 | Correct | 1359 ms | 315088 KB | Output is correct |
108 | Correct | 1279 ms | 340100 KB | Output is correct |
109 | Correct | 1151 ms | 308708 KB | Output is correct |
110 | Correct | 1314 ms | 340540 KB | Output is correct |
111 | Correct | 1101 ms | 310344 KB | Output is correct |
112 | Correct | 846 ms | 19080 KB | Output is correct |
113 | Correct | 840 ms | 19068 KB | Output is correct |
114 | Correct | 792 ms | 13672 KB | Output is correct |
115 | Correct | 804 ms | 13668 KB | Output is correct |
116 | Correct | 288 ms | 10212 KB | Output is correct |
117 | Correct | 299 ms | 10236 KB | Output is correct |
118 | Correct | 1523 ms | 415172 KB | Output is correct |
119 | Correct | 1336 ms | 339900 KB | Output is correct |
120 | Correct | 1187 ms | 308608 KB | Output is correct |
121 | Correct | 1376 ms | 415480 KB | Output is correct |
122 | Correct | 1129 ms | 338512 KB | Output is correct |
123 | Correct | 1056 ms | 308884 KB | Output is correct |
124 | Correct | 1368 ms | 415076 KB | Output is correct |
125 | Correct | 1167 ms | 339688 KB | Output is correct |
126 | Correct | 1138 ms | 307572 KB | Output is correct |