#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
#define endl '\n'
const int block = 300;
const int inf = 1234567890;
int bestval[maxn][block]; //all 0's is good
int bestdist[maxn][block]; //starts at all 0's which is good
int ndist[block];
int nval[block];
int bd[maxn]; //used for things that are greater than square root n
int bv[maxn];
bool cseen[maxn]; //used during the merge thing
bool illegal[maxn]; //used for queries greater than maxn
int N, M, Q;
vector<vector<int>> adj(maxn);
void merge(int x, int y) {
// cout << "merging: " << x << " into " << y << endl;
//merge everything from y into x (going to y will increase distance by 1)
int ind = -1;
int p1 = 0;
int p2 = 0;
while (++ind < block) { //run a merge-sort like algorithm
// cout << ind << " - " << block << endl;
cseen[0] = false;
while (cseen[bestval[x][p1]]) ++p1;
while (cseen[bestval[y][p2]]) ++p2;
if (bestdist[x][p1] > bestdist[y][p2]+1) {
ndist[ind] = bestdist[x][p1];
nval[ind] = bestval[x][p1];
p1++;
cseen[nval[ind]] = true;
}
else {
ndist[ind] = bestdist[y][p2]+1;
nval[ind] = bestval[y][p2];
p2++;
cseen[nval[ind]] = true;
}
}
for (int i = 0; i < block; i++) {
bestval[x][i] = nval[i];
bestdist[x][i] = ndist[i];
cseen[nval[i]] = false; //unmark it for the next iteration
}
}
void recalculate() {
for (int i = 1; i <= N; i++) {
bd[i] = 0;
if (!illegal[i]) {
bv[i] = i;
}
else {
bv[i] = 0;
bd[i] = -inf;
}
for (int val : adj[i]) {
if (bd[val] + 1 > bd[i]) {
bd[i] = bd[val]+1;
bv[i] = bv[val]; //don't think i actually need this but maybe
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M >> Q;
int ti; //party location in the query
int yi; //used for queries
int s, e; //used for edges
for (int i = 0; i < M; i++) {
cin >> s >> e; //reverse edges here
adj[e].push_back(s);
}
//process from back to front
for (int i = 1; i <= N; i++) {
// cout << "at: " << i << endl;
//want what can get to this (or what this gets to in reversed graph)
fill(bestdist[i], bestdist[i]+block, -inf);
//calculate everything for this
bestval[i][0] = i; //store myself
bestdist[i][0] = 0;
for (int val : adj[i]) {
merge(i, val);
}
// cout << "best dist for " << i << ": " << bestdist[i][0] << endl;
}
int cur;
while (Q--) {
// cout << "here: " << Q << endl;
cin >> ti >> yi;
vector<int> cl; //current illegal
for (int i = 0; i < yi; i++) {
cin >> cur;
cl.push_back(cur);
illegal[cur] = true;
}
//do processing
if (yi < block) {
//do first thing
int ind = 0;
while (illegal[bestval[ti][ind]]) {
// cout << ind << ": " << bestval[ti][ind] << endl;
ind++;
}
// cout << ind << ": " << bestval[ti][ind] << endl;
if (bestval[ti][ind] != 0 && bestdist[ti][ind] >= 0) {
cout << bestdist[ti][ind] << endl;
}
else cout << -1 << endl;
}
else {
recalculate();
if (bv[ti] != 0 && bd[ti] >= 0) {
cout << bd[ti] << endl;
//we just want the distance, not the index
}
else cout << -1 << endl;
}
//mark the things as ok again
for (int i = 0; i < yi; i++) {
illegal[cl[i]] = false;
}
}
cout.flush();
cin >> N;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2680 KB |
Output is correct |
2 |
Correct |
3 ms |
2804 KB |
Output is correct |
3 |
Correct |
4 ms |
2880 KB |
Output is correct |
4 |
Correct |
5 ms |
2880 KB |
Output is correct |
5 |
Correct |
11 ms |
5404 KB |
Output is correct |
6 |
Correct |
11 ms |
5404 KB |
Output is correct |
7 |
Correct |
12 ms |
5404 KB |
Output is correct |
8 |
Correct |
12 ms |
5404 KB |
Output is correct |
9 |
Correct |
14 ms |
5404 KB |
Output is correct |
10 |
Correct |
11 ms |
5404 KB |
Output is correct |
11 |
Correct |
11 ms |
5404 KB |
Output is correct |
12 |
Correct |
11 ms |
5404 KB |
Output is correct |
13 |
Correct |
10 ms |
5404 KB |
Output is correct |
14 |
Correct |
11 ms |
5404 KB |
Output is correct |
15 |
Correct |
13 ms |
5404 KB |
Output is correct |
16 |
Correct |
10 ms |
5404 KB |
Output is correct |
17 |
Correct |
11 ms |
5404 KB |
Output is correct |
18 |
Correct |
12 ms |
5404 KB |
Output is correct |
19 |
Correct |
11 ms |
5404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2680 KB |
Output is correct |
2 |
Correct |
3 ms |
2804 KB |
Output is correct |
3 |
Correct |
4 ms |
2880 KB |
Output is correct |
4 |
Correct |
5 ms |
2880 KB |
Output is correct |
5 |
Correct |
11 ms |
5404 KB |
Output is correct |
6 |
Correct |
11 ms |
5404 KB |
Output is correct |
7 |
Correct |
12 ms |
5404 KB |
Output is correct |
8 |
Correct |
12 ms |
5404 KB |
Output is correct |
9 |
Correct |
14 ms |
5404 KB |
Output is correct |
10 |
Correct |
11 ms |
5404 KB |
Output is correct |
11 |
Correct |
11 ms |
5404 KB |
Output is correct |
12 |
Correct |
11 ms |
5404 KB |
Output is correct |
13 |
Correct |
10 ms |
5404 KB |
Output is correct |
14 |
Correct |
11 ms |
5404 KB |
Output is correct |
15 |
Correct |
13 ms |
5404 KB |
Output is correct |
16 |
Correct |
10 ms |
5404 KB |
Output is correct |
17 |
Correct |
11 ms |
5404 KB |
Output is correct |
18 |
Correct |
12 ms |
5404 KB |
Output is correct |
19 |
Correct |
11 ms |
5404 KB |
Output is correct |
20 |
Correct |
404 ms |
6596 KB |
Output is correct |
21 |
Correct |
409 ms |
6732 KB |
Output is correct |
22 |
Correct |
395 ms |
6780 KB |
Output is correct |
23 |
Correct |
423 ms |
6780 KB |
Output is correct |
24 |
Correct |
1146 ms |
242044 KB |
Output is correct |
25 |
Correct |
980 ms |
242084 KB |
Output is correct |
26 |
Correct |
1054 ms |
242084 KB |
Output is correct |
27 |
Correct |
778 ms |
242352 KB |
Output is correct |
28 |
Correct |
749 ms |
242352 KB |
Output is correct |
29 |
Correct |
702 ms |
242352 KB |
Output is correct |
30 |
Correct |
867 ms |
242352 KB |
Output is correct |
31 |
Correct |
842 ms |
242352 KB |
Output is correct |
32 |
Correct |
758 ms |
242352 KB |
Output is correct |
33 |
Correct |
752 ms |
242352 KB |
Output is correct |
34 |
Correct |
822 ms |
242352 KB |
Output is correct |
35 |
Correct |
774 ms |
242352 KB |
Output is correct |
36 |
Correct |
738 ms |
242352 KB |
Output is correct |
37 |
Correct |
755 ms |
242352 KB |
Output is correct |
38 |
Correct |
733 ms |
242352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2680 KB |
Output is correct |
2 |
Correct |
3 ms |
2804 KB |
Output is correct |
3 |
Correct |
4 ms |
2880 KB |
Output is correct |
4 |
Correct |
5 ms |
2880 KB |
Output is correct |
5 |
Correct |
11 ms |
5404 KB |
Output is correct |
6 |
Correct |
11 ms |
5404 KB |
Output is correct |
7 |
Correct |
12 ms |
5404 KB |
Output is correct |
8 |
Correct |
12 ms |
5404 KB |
Output is correct |
9 |
Correct |
14 ms |
5404 KB |
Output is correct |
10 |
Correct |
11 ms |
5404 KB |
Output is correct |
11 |
Correct |
11 ms |
5404 KB |
Output is correct |
12 |
Correct |
11 ms |
5404 KB |
Output is correct |
13 |
Correct |
10 ms |
5404 KB |
Output is correct |
14 |
Correct |
11 ms |
5404 KB |
Output is correct |
15 |
Correct |
13 ms |
5404 KB |
Output is correct |
16 |
Correct |
10 ms |
5404 KB |
Output is correct |
17 |
Correct |
11 ms |
5404 KB |
Output is correct |
18 |
Correct |
12 ms |
5404 KB |
Output is correct |
19 |
Correct |
11 ms |
5404 KB |
Output is correct |
20 |
Correct |
404 ms |
6596 KB |
Output is correct |
21 |
Correct |
409 ms |
6732 KB |
Output is correct |
22 |
Correct |
395 ms |
6780 KB |
Output is correct |
23 |
Correct |
423 ms |
6780 KB |
Output is correct |
24 |
Correct |
1146 ms |
242044 KB |
Output is correct |
25 |
Correct |
980 ms |
242084 KB |
Output is correct |
26 |
Correct |
1054 ms |
242084 KB |
Output is correct |
27 |
Correct |
778 ms |
242352 KB |
Output is correct |
28 |
Correct |
749 ms |
242352 KB |
Output is correct |
29 |
Correct |
702 ms |
242352 KB |
Output is correct |
30 |
Correct |
867 ms |
242352 KB |
Output is correct |
31 |
Correct |
842 ms |
242352 KB |
Output is correct |
32 |
Correct |
758 ms |
242352 KB |
Output is correct |
33 |
Correct |
752 ms |
242352 KB |
Output is correct |
34 |
Correct |
822 ms |
242352 KB |
Output is correct |
35 |
Correct |
774 ms |
242352 KB |
Output is correct |
36 |
Correct |
738 ms |
242352 KB |
Output is correct |
37 |
Correct |
755 ms |
242352 KB |
Output is correct |
38 |
Correct |
733 ms |
242352 KB |
Output is correct |
39 |
Correct |
968 ms |
242352 KB |
Output is correct |
40 |
Correct |
1049 ms |
242352 KB |
Output is correct |
41 |
Correct |
1293 ms |
242352 KB |
Output is correct |
42 |
Correct |
1581 ms |
242352 KB |
Output is correct |
43 |
Correct |
985 ms |
242352 KB |
Output is correct |
44 |
Correct |
433 ms |
242352 KB |
Output is correct |
45 |
Correct |
420 ms |
242352 KB |
Output is correct |
46 |
Correct |
425 ms |
242352 KB |
Output is correct |
47 |
Correct |
441 ms |
242352 KB |
Output is correct |
48 |
Correct |
402 ms |
242352 KB |
Output is correct |
49 |
Correct |
767 ms |
242352 KB |
Output is correct |
50 |
Correct |
709 ms |
242352 KB |
Output is correct |
51 |
Correct |
424 ms |
242352 KB |
Output is correct |
52 |
Correct |
426 ms |
242352 KB |
Output is correct |
53 |
Correct |
793 ms |
242352 KB |
Output is correct |
54 |
Correct |
1029 ms |
242352 KB |
Output is correct |
55 |
Correct |
771 ms |
242352 KB |
Output is correct |
56 |
Correct |
1093 ms |
242352 KB |
Output is correct |
57 |
Correct |
444 ms |
242352 KB |
Output is correct |
58 |
Correct |
459 ms |
242352 KB |
Output is correct |
59 |
Correct |
409 ms |
242352 KB |
Output is correct |
60 |
Correct |
419 ms |
242352 KB |
Output is correct |
61 |
Correct |
978 ms |
242352 KB |
Output is correct |
62 |
Correct |
1053 ms |
242352 KB |
Output is correct |
63 |
Correct |
1575 ms |
242352 KB |
Output is correct |
64 |
Correct |
1287 ms |
242352 KB |
Output is correct |
65 |
Correct |
1820 ms |
242352 KB |
Output is correct |
66 |
Correct |
1625 ms |
242352 KB |
Output is correct |
67 |
Correct |
741 ms |
242352 KB |
Output is correct |
68 |
Correct |
775 ms |
242352 KB |
Output is correct |
69 |
Correct |
851 ms |
242352 KB |
Output is correct |
70 |
Correct |
842 ms |
242352 KB |
Output is correct |
71 |
Correct |
942 ms |
242352 KB |
Output is correct |
72 |
Correct |
854 ms |
242352 KB |
Output is correct |
73 |
Correct |
930 ms |
242352 KB |
Output is correct |
74 |
Correct |
870 ms |
242352 KB |
Output is correct |
75 |
Correct |
879 ms |
242352 KB |
Output is correct |
76 |
Correct |
901 ms |
242352 KB |
Output is correct |
77 |
Correct |
776 ms |
242352 KB |
Output is correct |
78 |
Correct |
780 ms |
242352 KB |
Output is correct |
79 |
Correct |
426 ms |
242352 KB |
Output is correct |
80 |
Correct |
399 ms |
242352 KB |
Output is correct |
81 |
Correct |
420 ms |
242352 KB |
Output is correct |
82 |
Correct |
882 ms |
242352 KB |
Output is correct |
83 |
Correct |
920 ms |
242352 KB |
Output is correct |
84 |
Correct |
791 ms |
242352 KB |
Output is correct |
85 |
Correct |
973 ms |
242352 KB |
Output is correct |
86 |
Correct |
832 ms |
242352 KB |
Output is correct |
87 |
Correct |
838 ms |
242352 KB |
Output is correct |
88 |
Correct |
449 ms |
242352 KB |
Output is correct |
89 |
Correct |
447 ms |
242352 KB |
Output is correct |
90 |
Correct |
428 ms |
242352 KB |
Output is correct |
91 |
Correct |
408 ms |
242352 KB |
Output is correct |
92 |
Correct |
403 ms |
242352 KB |
Output is correct |
93 |
Correct |
401 ms |
242352 KB |
Output is correct |
94 |
Correct |
811 ms |
242352 KB |
Output is correct |
95 |
Correct |
830 ms |
242352 KB |
Output is correct |
96 |
Correct |
744 ms |
242352 KB |
Output is correct |
97 |
Correct |
881 ms |
242352 KB |
Output is correct |
98 |
Correct |
852 ms |
242352 KB |
Output is correct |
99 |
Correct |
832 ms |
242352 KB |
Output is correct |
100 |
Correct |
446 ms |
242352 KB |
Output is correct |
101 |
Correct |
456 ms |
242352 KB |
Output is correct |
102 |
Correct |
418 ms |
242352 KB |
Output is correct |
103 |
Correct |
423 ms |
242352 KB |
Output is correct |
104 |
Correct |
409 ms |
242352 KB |
Output is correct |
105 |
Correct |
402 ms |
242352 KB |
Output is correct |
106 |
Correct |
778 ms |
242352 KB |
Output is correct |
107 |
Correct |
910 ms |
242352 KB |
Output is correct |
108 |
Correct |
777 ms |
242352 KB |
Output is correct |
109 |
Correct |
749 ms |
242352 KB |
Output is correct |
110 |
Correct |
778 ms |
242352 KB |
Output is correct |
111 |
Correct |
814 ms |
242352 KB |
Output is correct |
112 |
Correct |
433 ms |
242352 KB |
Output is correct |
113 |
Correct |
454 ms |
242352 KB |
Output is correct |
114 |
Correct |
410 ms |
242352 KB |
Output is correct |
115 |
Correct |
415 ms |
242352 KB |
Output is correct |
116 |
Correct |
394 ms |
242352 KB |
Output is correct |
117 |
Correct |
403 ms |
242352 KB |
Output is correct |
118 |
Correct |
814 ms |
242352 KB |
Output is correct |
119 |
Correct |
798 ms |
242352 KB |
Output is correct |
120 |
Correct |
883 ms |
242352 KB |
Output is correct |
121 |
Correct |
746 ms |
242352 KB |
Output is correct |
122 |
Correct |
739 ms |
242352 KB |
Output is correct |
123 |
Correct |
769 ms |
242352 KB |
Output is correct |
124 |
Correct |
956 ms |
242352 KB |
Output is correct |
125 |
Correct |
802 ms |
242352 KB |
Output is correct |
126 |
Correct |
779 ms |
242352 KB |
Output is correct |