oj.uz

Submission #930516

# Submission time Handle Problem Language Result Execution time Memory
930516 2024-02-20T05:20:22 Z iskhakkutbilim Bitaro’s Party (JOI18_bitaro) C++17
100 / 100
 1188 ms 421072 KB 
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 1e5;
const int SZ = 400;
vector<int> g[N+5], gg[N+5];
vector<pair<int,int> > calc[N+1];
signed main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	int n, m, q; cin >> n >> m >> q;
	for(int i = 0;i < m; i++){
		int a, b; cin >> a >> b;
		g[a].push_back(b);
		gg[b].push_back(a);
	}
	
	
	vector<int> reach, dist(n+1), last(n+1, 0);
	for(int i = 1;i <= n; i++){
		reach.push_back(i);
		for(auto to : gg[i]){
			for(auto [d, u] : calc[to]){
				if(last[u] == i){
					dist[u] = max(dist[u], d + 1);
				}else{
					dist[u] = d + 1;
					last[u] = i;
					reach.push_back(u);
				}
			}
		}
		sort(all(reach),[&](int a, int b){
			return dist[a] > dist[b];
		});
		for(int j = 0;j < min(SZ, (int)reach.size()); j++){
			calc[i].push_back({dist[reach[j]], reach[j]});
		}
		reach.clear();
	}
	
	
	
	int timer = 1;
	vector<int> del(n+1, 0);
	while(q--){
		int v, k; cin >> v >> k;
		for(int i = 0;i < k; i++){
			int x; cin >> x;
			del[x] = timer;
		}
		
		
		if(k < SZ){
			int ans = -1;
			for(auto [d, u] : calc[v]){
				if(del[u] != timer){
					ans = d;
					break;
				}
			}
			cout << ans << '\n';
		}else{
			vector<int> d(n+1, -1);
			
			for(int i = 1;i <= n; i++){				
				if(del[i] != timer){
					d[i] = max(d[i], 0);
				}
				for(int to : g[i]){
					if(d[i] != -1)
					d[to] = max(d[to], d[i] + 1);
				}
			}
			cout << d[v] << '\n';
		}
		
		
		
		
		timer++;
	}
	
	
	
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 3 ms 7772 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 3 ms 7768 KB Output is correct
8 Correct 11 ms 10800 KB Output is correct
9 Correct 11 ms 10844 KB Output is correct
10 Correct 11 ms 10844 KB Output is correct
11 Correct 11 ms 10500 KB Output is correct
12 Correct 6 ms 8796 KB Output is correct
13 Correct 10 ms 10332 KB Output is correct
14 Correct 8 ms 9384 KB Output is correct
15 Correct 5 ms 8284 KB Output is correct
16 Correct 14 ms 9632 KB Output is correct
17 Correct 9 ms 9560 KB Output is correct
18 Correct 5 ms 8540 KB Output is correct
19 Correct 8 ms 9668 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 3 ms 7772 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 3 ms 7768 KB Output is correct
8 Correct 11 ms 10800 KB Output is correct
9 Correct 11 ms 10844 KB Output is correct
10 Correct 11 ms 10844 KB Output is correct
11 Correct 11 ms 10500 KB Output is correct
12 Correct 6 ms 8796 KB Output is correct
13 Correct 10 ms 10332 KB Output is correct
14 Correct 8 ms 9384 KB Output is correct
15 Correct 5 ms 8284 KB Output is correct
16 Correct 14 ms 9632 KB Output is correct
17 Correct 9 ms 9560 KB Output is correct
18 Correct 5 ms 8540 KB Output is correct
19 Correct 8 ms 9668 KB Output is correct
20 Correct 112 ms 14620 KB Output is correct
21 Correct 109 ms 14816 KB Output is correct
22 Correct 108 ms 14752 KB Output is correct
23 Correct 130 ms 14688 KB Output is correct
24 Correct 938 ms 259780 KB Output is correct
25 Correct 999 ms 271152 KB Output is correct
26 Correct 988 ms 270224 KB Output is correct
27 Correct 962 ms 419896 KB Output is correct
28 Correct 934 ms 419700 KB Output is correct
29 Correct 943 ms 419936 KB Output is correct
30 Correct 974 ms 418808 KB Output is correct
31 Correct 1131 ms 404308 KB Output is correct
32 Correct 968 ms 418784 KB Output is correct
33 Correct 800 ms 261648 KB Output is correct
34 Correct 852 ms 215504 KB Output is correct
35 Correct 818 ms 260176 KB Output is correct
36 Correct 973 ms 340508 KB Output is correct
37 Correct 1092 ms 308956 KB Output is correct
38 Correct 965 ms 341616 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 3 ms 7772 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 3 ms 7768 KB Output is correct
8 Correct 11 ms 10800 KB Output is correct
9 Correct 11 ms 10844 KB Output is correct
10 Correct 11 ms 10844 KB Output is correct
11 Correct 11 ms 10500 KB Output is correct
12 Correct 6 ms 8796 KB Output is correct
13 Correct 10 ms 10332 KB Output is correct
14 Correct 8 ms 9384 KB Output is correct
15 Correct 5 ms 8284 KB Output is correct
16 Correct 14 ms 9632 KB Output is correct
17 Correct 9 ms 9560 KB Output is correct
18 Correct 5 ms 8540 KB Output is correct
19 Correct 8 ms 9668 KB Output is correct
20 Correct 112 ms 14620 KB Output is correct
21 Correct 109 ms 14816 KB Output is correct
22 Correct 108 ms 14752 KB Output is correct
23 Correct 130 ms 14688 KB Output is correct
24 Correct 938 ms 259780 KB Output is correct
25 Correct 999 ms 271152 KB Output is correct
26 Correct 988 ms 270224 KB Output is correct
27 Correct 962 ms 419896 KB Output is correct
28 Correct 934 ms 419700 KB Output is correct
29 Correct 943 ms 419936 KB Output is correct
30 Correct 974 ms 418808 KB Output is correct
31 Correct 1131 ms 404308 KB Output is correct
32 Correct 968 ms 418784 KB Output is correct
33 Correct 800 ms 261648 KB Output is correct
34 Correct 852 ms 215504 KB Output is correct
35 Correct 818 ms 260176 KB Output is correct
36 Correct 973 ms 340508 KB Output is correct
37 Correct 1092 ms 308956 KB Output is correct
38 Correct 965 ms 341616 KB Output is correct
39 Correct 979 ms 263904 KB Output is correct
40 Correct 958 ms 265388 KB Output is correct
41 Correct 963 ms 268112 KB Output is correct
42 Correct 1059 ms 266176 KB Output is correct
43 Correct 976 ms 265784 KB Output is correct
44 Correct 129 ms 15956 KB Output is correct
45 Correct 113 ms 15148 KB Output is correct
46 Correct 110 ms 15148 KB Output is correct
47 Correct 131 ms 14932 KB Output is correct
48 Correct 111 ms 14672 KB Output is correct
49 Correct 980 ms 420852 KB Output is correct
50 Correct 936 ms 419504 KB Output is correct
51 Correct 126 ms 16268 KB Output is correct
52 Correct 114 ms 14928 KB Output is correct
53 Correct 995 ms 339792 KB Output is correct
54 Correct 1130 ms 309840 KB Output is correct
55 Correct 959 ms 339216 KB Output is correct
56 Correct 1090 ms 309580 KB Output is correct
57 Correct 132 ms 15956 KB Output is correct
58 Correct 128 ms 15696 KB Output is correct
59 Correct 123 ms 14940 KB Output is correct
60 Correct 113 ms 14952 KB Output is correct
61 Correct 1037 ms 420168 KB Output is correct
62 Correct 1059 ms 341184 KB Output is correct
63 Correct 1144 ms 308664 KB Output is correct
64 Correct 934 ms 419736 KB Output is correct
65 Correct 952 ms 339024 KB Output is correct
66 Correct 1132 ms 309808 KB Output is correct
67 Correct 935 ms 419356 KB Output is correct
68 Correct 974 ms 340604 KB Output is correct
69 Correct 1051 ms 305936 KB Output is correct
70 Correct 930 ms 420088 KB Output is correct
71 Correct 975 ms 340940 KB Output is correct
72 Correct 1108 ms 309496 KB Output is correct
73 Correct 966 ms 420000 KB Output is correct
74 Correct 979 ms 340924 KB Output is correct
75 Correct 1064 ms 309644 KB Output is correct
76 Correct 960 ms 421072 KB Output is correct
77 Correct 933 ms 419636 KB Output is correct
78 Correct 954 ms 420300 KB Output is correct
79 Correct 126 ms 15908 KB Output is correct
80 Correct 119 ms 15100 KB Output is correct
81 Correct 109 ms 14672 KB Output is correct
82 Correct 1024 ms 419932 KB Output is correct
83 Correct 1173 ms 405716 KB Output is correct
84 Correct 972 ms 418716 KB Output is correct
85 Correct 1188 ms 403628 KB Output is correct
86 Correct 987 ms 418996 KB Output is correct
87 Correct 1179 ms 405156 KB Output is correct
88 Correct 126 ms 15956 KB Output is correct
89 Correct 128 ms 16208 KB Output is correct
90 Correct 111 ms 14932 KB Output is correct
91 Correct 109 ms 15188 KB Output is correct
92 Correct 107 ms 14676 KB Output is correct
93 Correct 112 ms 14672 KB Output is correct
94 Correct 830 ms 263084 KB Output is correct
95 Correct 899 ms 215504 KB Output is correct
96 Correct 805 ms 260224 KB Output is correct
97 Correct 892 ms 218344 KB Output is correct
98 Correct 814 ms 261568 KB Output is correct
99 Correct 885 ms 218004 KB Output is correct
100 Correct 151 ms 16196 KB Output is correct
101 Correct 143 ms 15928 KB Output is correct
102 Correct 130 ms 15044 KB Output is correct
103 Correct 128 ms 15184 KB Output is correct
104 Correct 133 ms 14932 KB Output is correct
105 Correct 125 ms 14672 KB Output is correct
106 Correct 988 ms 340560 KB Output is correct
107 Correct 1112 ms 310364 KB Output is correct
108 Correct 987 ms 341624 KB Output is correct
109 Correct 1061 ms 308836 KB Output is correct
110 Correct 963 ms 342224 KB Output is correct
111 Correct 1110 ms 310256 KB Output is correct
112 Correct 126 ms 15944 KB Output is correct
113 Correct 126 ms 15952 KB Output is correct
114 Correct 115 ms 15168 KB Output is correct
115 Correct 112 ms 15188 KB Output is correct
116 Correct 107 ms 14624 KB Output is correct
117 Correct 109 ms 14840 KB Output is correct
118 Correct 959 ms 419392 KB Output is correct
119 Correct 973 ms 341512 KB Output is correct
120 Correct 1084 ms 308500 KB Output is correct
121 Correct 944 ms 419652 KB Output is correct
122 Correct 960 ms 340124 KB Output is correct
123 Correct 1070 ms 308684 KB Output is correct
124 Correct 944 ms 419476 KB Output is correct
125 Correct 988 ms 341400 KB Output is correct
126 Correct 1072 ms 307684 KB Output is correct