oj.uz

Submission #776282

# Submission time Handle Problem Language Result Execution time Memory
776282 2023-07-07T14:34:32 Z taitruong270 Bitaro’s Party (JOI18_bitaro) C++17
100 / 100
 912 ms 150860 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int mxN = (int)2e5+2;
const int B = 100;

int n, m, Q, a, b;
vector<int> adj[mxN], cur;
vector<array<int,2>> node[mxN];
int bad[mxN], vis[mxN], dis[mxN], dp[mxN];

int main() {
	cin >> n >> m >> Q;
	for(int i = 0; i < m; i++)
		cin >> a >> b, adj[b].pb(a);
	for(int i = 1; i <= n; i++, cur.clear()){
		for(auto j : adj[i]){
			for(auto [w,u] : node[j]){
				if(vis[u]==i) dis[u] = max(dis[u], w+1);
				else vis[u]=i, dis[u] = w+1, cur.pb(u);
			}
		}
		for(auto u : cur) node[i].pb({dis[u],u});
		node[i].pb({0,i}); sort(rbegin(node[i]),rend(node[i]));
		if(node[i].size()>B) node[i].erase(begin(node[i])+B,end(node[i]));
	}
	for(int q = 1; q <= Q; q++){
		int t, k, x, ans=-1; cin >> t >> k;
		for(int i = 0; i < k; i++) cin >> x, bad[x]=q;
		if(k<B){
			for(auto [w,u] : node[t]){
				if(bad[u]!=q){ ans=w; break; }
			}
		}
		else{
			fill(dp, dp+n+1, -1);
			for(int i = 1; i <= t; i++){
				if(bad[i]!=q) dp[i]=0;
				for(auto j : adj[i]) if(dp[j]!=-1) 
					dp[i] = max(dp[i],dp[j]+1);
			}
			ans = dp[t];
		}
		cout << ans << "\n";
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9700 KB Output is correct
5 Correct 7 ms 10104 KB Output is correct
6 Correct 7 ms 10196 KB Output is correct
7 Correct 8 ms 10196 KB Output is correct
8 Correct 9 ms 10728 KB Output is correct
9 Correct 9 ms 10648 KB Output is correct
10 Correct 8 ms 10652 KB Output is correct
11 Correct 8 ms 10708 KB Output is correct
12 Correct 9 ms 10524 KB Output is correct
13 Correct 8 ms 10580 KB Output is correct
14 Correct 12 ms 10364 KB Output is correct
15 Correct 12 ms 10356 KB Output is correct
16 Correct 10 ms 10356 KB Output is correct
17 Correct 9 ms 10484 KB Output is correct
18 Correct 8 ms 10324 KB Output is correct
19 Correct 8 ms 10452 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9700 KB Output is correct
5 Correct 7 ms 10104 KB Output is correct
6 Correct 7 ms 10196 KB Output is correct
7 Correct 8 ms 10196 KB Output is correct
8 Correct 9 ms 10728 KB Output is correct
9 Correct 9 ms 10648 KB Output is correct
10 Correct 8 ms 10652 KB Output is correct
11 Correct 8 ms 10708 KB Output is correct
12 Correct 9 ms 10524 KB Output is correct
13 Correct 8 ms 10580 KB Output is correct
14 Correct 12 ms 10364 KB Output is correct
15 Correct 12 ms 10356 KB Output is correct
16 Correct 10 ms 10356 KB Output is correct
17 Correct 9 ms 10484 KB Output is correct
18 Correct 8 ms 10324 KB Output is correct
19 Correct 8 ms 10452 KB Output is correct
20 Correct 93 ms 13312 KB Output is correct
21 Correct 97 ms 13332 KB Output is correct
22 Correct 102 ms 13260 KB Output is correct
23 Correct 103 ms 13332 KB Output is correct
24 Correct 643 ms 120900 KB Output is correct
25 Correct 715 ms 117324 KB Output is correct
26 Correct 638 ms 116812 KB Output is correct
27 Correct 419 ms 118084 KB Output is correct
28 Correct 418 ms 117968 KB Output is correct
29 Correct 441 ms 117824 KB Output is correct
30 Correct 426 ms 117940 KB Output is correct
31 Correct 555 ms 135916 KB Output is correct
32 Correct 418 ms 117716 KB Output is correct
33 Correct 382 ms 82696 KB Output is correct
34 Correct 577 ms 110156 KB Output is correct
35 Correct 377 ms 82320 KB Output is correct
36 Correct 411 ms 99504 KB Output is correct
37 Correct 620 ms 121224 KB Output is correct
38 Correct 419 ms 99428 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9700 KB Output is correct
5 Correct 7 ms 10104 KB Output is correct
6 Correct 7 ms 10196 KB Output is correct
7 Correct 8 ms 10196 KB Output is correct
8 Correct 9 ms 10728 KB Output is correct
9 Correct 9 ms 10648 KB Output is correct
10 Correct 8 ms 10652 KB Output is correct
11 Correct 8 ms 10708 KB Output is correct
12 Correct 9 ms 10524 KB Output is correct
13 Correct 8 ms 10580 KB Output is correct
14 Correct 12 ms 10364 KB Output is correct
15 Correct 12 ms 10356 KB Output is correct
16 Correct 10 ms 10356 KB Output is correct
17 Correct 9 ms 10484 KB Output is correct
18 Correct 8 ms 10324 KB Output is correct
19 Correct 8 ms 10452 KB Output is correct
20 Correct 93 ms 13312 KB Output is correct
21 Correct 97 ms 13332 KB Output is correct
22 Correct 102 ms 13260 KB Output is correct
23 Correct 103 ms 13332 KB Output is correct
24 Correct 643 ms 120900 KB Output is correct
25 Correct 715 ms 117324 KB Output is correct
26 Correct 638 ms 116812 KB Output is correct
27 Correct 419 ms 118084 KB Output is correct
28 Correct 418 ms 117968 KB Output is correct
29 Correct 441 ms 117824 KB Output is correct
30 Correct 426 ms 117940 KB Output is correct
31 Correct 555 ms 135916 KB Output is correct
32 Correct 418 ms 117716 KB Output is correct
33 Correct 382 ms 82696 KB Output is correct
34 Correct 577 ms 110156 KB Output is correct
35 Correct 377 ms 82320 KB Output is correct
36 Correct 411 ms 99504 KB Output is correct
37 Correct 620 ms 121224 KB Output is correct
38 Correct 419 ms 99428 KB Output is correct
39 Correct 877 ms 123320 KB Output is correct
40 Correct 652 ms 118700 KB Output is correct
41 Correct 912 ms 120048 KB Output is correct
42 Correct 705 ms 119312 KB Output is correct
43 Correct 645 ms 121068 KB Output is correct
44 Correct 280 ms 14628 KB Output is correct
45 Correct 119 ms 13824 KB Output is correct
46 Correct 161 ms 13776 KB Output is correct
47 Correct 125 ms 13516 KB Output is correct
48 Correct 101 ms 13364 KB Output is correct
49 Correct 571 ms 118432 KB Output is correct
50 Correct 699 ms 117488 KB Output is correct
51 Correct 265 ms 14452 KB Output is correct
52 Correct 252 ms 13552 KB Output is correct
53 Correct 558 ms 99532 KB Output is correct
54 Correct 752 ms 120492 KB Output is correct
55 Correct 671 ms 98924 KB Output is correct
56 Correct 859 ms 123592 KB Output is correct
57 Correct 236 ms 14408 KB Output is correct
58 Correct 254 ms 14476 KB Output is correct
59 Correct 255 ms 13560 KB Output is correct
60 Correct 252 ms 13660 KB Output is correct
61 Correct 466 ms 117652 KB Output is correct
62 Correct 469 ms 99288 KB Output is correct
63 Correct 641 ms 119192 KB Output is correct
64 Correct 566 ms 117564 KB Output is correct
65 Correct 568 ms 99020 KB Output is correct
66 Correct 786 ms 121068 KB Output is correct
67 Correct 634 ms 117580 KB Output is correct
68 Correct 677 ms 99272 KB Output is correct
69 Correct 867 ms 121220 KB Output is correct
70 Correct 440 ms 117724 KB Output is correct
71 Correct 421 ms 99276 KB Output is correct
72 Correct 605 ms 121164 KB Output is correct
73 Correct 432 ms 117776 KB Output is correct
74 Correct 432 ms 99244 KB Output is correct
75 Correct 624 ms 123340 KB Output is correct
76 Correct 613 ms 119176 KB Output is correct
77 Correct 646 ms 118276 KB Output is correct
78 Correct 434 ms 118308 KB Output is correct
79 Correct 247 ms 14560 KB Output is correct
80 Correct 156 ms 13748 KB Output is correct
81 Correct 100 ms 13260 KB Output is correct
82 Correct 605 ms 119024 KB Output is correct
83 Correct 776 ms 140356 KB Output is correct
84 Correct 643 ms 118192 KB Output is correct
85 Correct 827 ms 150860 KB Output is correct
86 Correct 436 ms 118140 KB Output is correct
87 Correct 593 ms 139388 KB Output is correct
88 Correct 249 ms 14704 KB Output is correct
89 Correct 253 ms 14584 KB Output is correct
90 Correct 164 ms 13764 KB Output is correct
91 Correct 167 ms 13736 KB Output is correct
92 Correct 97 ms 13312 KB Output is correct
93 Correct 95 ms 13308 KB Output is correct
94 Correct 556 ms 83964 KB Output is correct
95 Correct 796 ms 118028 KB Output is correct
96 Correct 592 ms 82932 KB Output is correct
97 Correct 828 ms 118196 KB Output is correct
98 Correct 437 ms 83296 KB Output is correct
99 Correct 619 ms 114056 KB Output is correct
100 Correct 244 ms 14672 KB Output is correct
101 Correct 271 ms 14672 KB Output is correct
102 Correct 158 ms 13784 KB Output is correct
103 Correct 144 ms 13768 KB Output is correct
104 Correct 102 ms 13324 KB Output is correct
105 Correct 106 ms 13392 KB Output is correct
106 Correct 577 ms 100360 KB Output is correct
107 Correct 787 ms 126624 KB Output is correct
108 Correct 703 ms 100076 KB Output is correct
109 Correct 829 ms 117540 KB Output is correct
110 Correct 469 ms 100076 KB Output is correct
111 Correct 619 ms 122844 KB Output is correct
112 Correct 245 ms 14668 KB Output is correct
113 Correct 252 ms 14676 KB Output is correct
114 Correct 157 ms 13700 KB Output is correct
115 Correct 157 ms 13616 KB Output is correct
116 Correct 103 ms 13280 KB Output is correct
117 Correct 97 ms 13280 KB Output is correct
118 Correct 452 ms 117244 KB Output is correct
119 Correct 414 ms 98988 KB Output is correct
120 Correct 641 ms 126288 KB Output is correct
121 Correct 430 ms 117192 KB Output is correct
122 Correct 437 ms 98656 KB Output is correct
123 Correct 666 ms 125528 KB Output is correct
124 Correct 422 ms 117096 KB Output is correct
125 Correct 420 ms 99072 KB Output is correct
126 Correct 613 ms 122156 KB Output is correct