oj.uz

Submission #751293

# Submission time Handle Problem Language Result Execution time Memory
751293 2023-05-31T10:57:43 Z Dan4Life Bitaro’s Party (JOI18_bitaro) C++17
100 / 100
 1405 ms 118188 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int mxN = (int)2e5+2;
const int B = 75;

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 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9720 KB Output is correct
4 Correct 5 ms 9720 KB Output is correct
5 Correct 8 ms 10196 KB Output is correct
6 Correct 9 ms 10196 KB Output is correct
7 Correct 11 ms 10068 KB Output is correct
8 Correct 9 ms 10708 KB Output is correct
9 Correct 9 ms 10708 KB Output is correct
10 Correct 9 ms 10628 KB Output is correct
11 Correct 9 ms 10580 KB Output is correct
12 Correct 11 ms 10452 KB Output is correct
13 Correct 9 ms 10692 KB Output is correct
14 Correct 8 ms 10324 KB Output is correct
15 Correct 9 ms 10196 KB Output is correct
16 Correct 8 ms 10228 KB Output is correct
17 Correct 9 ms 10480 KB Output is correct
18 Correct 8 ms 10304 KB Output is correct
19 Correct 9 ms 10452 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9720 KB Output is correct
4 Correct 5 ms 9720 KB Output is correct
5 Correct 8 ms 10196 KB Output is correct
6 Correct 9 ms 10196 KB Output is correct
7 Correct 11 ms 10068 KB Output is correct
8 Correct 9 ms 10708 KB Output is correct
9 Correct 9 ms 10708 KB Output is correct
10 Correct 9 ms 10628 KB Output is correct
11 Correct 9 ms 10580 KB Output is correct
12 Correct 11 ms 10452 KB Output is correct
13 Correct 9 ms 10692 KB Output is correct
14 Correct 8 ms 10324 KB Output is correct
15 Correct 9 ms 10196 KB Output is correct
16 Correct 8 ms 10228 KB Output is correct
17 Correct 9 ms 10480 KB Output is correct
18 Correct 8 ms 10304 KB Output is correct
19 Correct 9 ms 10452 KB Output is correct
20 Correct 142 ms 11800 KB Output is correct
21 Correct 133 ms 11732 KB Output is correct
22 Correct 132 ms 11836 KB Output is correct
23 Correct 137 ms 11820 KB Output is correct
24 Correct 583 ms 94124 KB Output is correct
25 Correct 591 ms 93748 KB Output is correct
26 Correct 591 ms 93448 KB Output is correct
27 Correct 452 ms 115480 KB Output is correct
28 Correct 491 ms 115360 KB Output is correct
29 Correct 447 ms 115148 KB Output is correct
30 Correct 482 ms 115276 KB Output is correct
31 Correct 564 ms 116024 KB Output is correct
32 Correct 503 ms 115188 KB Output is correct
33 Correct 424 ms 78768 KB Output is correct
34 Correct 570 ms 93916 KB Output is correct
35 Correct 413 ms 78124 KB Output is correct
36 Correct 479 ms 96816 KB Output is correct
37 Correct 619 ms 96808 KB Output is correct
38 Correct 531 ms 96888 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9720 KB Output is correct
4 Correct 5 ms 9720 KB Output is correct
5 Correct 8 ms 10196 KB Output is correct
6 Correct 9 ms 10196 KB Output is correct
7 Correct 11 ms 10068 KB Output is correct
8 Correct 9 ms 10708 KB Output is correct
9 Correct 9 ms 10708 KB Output is correct
10 Correct 9 ms 10628 KB Output is correct
11 Correct 9 ms 10580 KB Output is correct
12 Correct 11 ms 10452 KB Output is correct
13 Correct 9 ms 10692 KB Output is correct
14 Correct 8 ms 10324 KB Output is correct
15 Correct 9 ms 10196 KB Output is correct
16 Correct 8 ms 10228 KB Output is correct
17 Correct 9 ms 10480 KB Output is correct
18 Correct 8 ms 10304 KB Output is correct
19 Correct 9 ms 10452 KB Output is correct
20 Correct 142 ms 11800 KB Output is correct
21 Correct 133 ms 11732 KB Output is correct
22 Correct 132 ms 11836 KB Output is correct
23 Correct 137 ms 11820 KB Output is correct
24 Correct 583 ms 94124 KB Output is correct
25 Correct 591 ms 93748 KB Output is correct
26 Correct 591 ms 93448 KB Output is correct
27 Correct 452 ms 115480 KB Output is correct
28 Correct 491 ms 115360 KB Output is correct
29 Correct 447 ms 115148 KB Output is correct
30 Correct 482 ms 115276 KB Output is correct
31 Correct 564 ms 116024 KB Output is correct
32 Correct 503 ms 115188 KB Output is correct
33 Correct 424 ms 78768 KB Output is correct
34 Correct 570 ms 93916 KB Output is correct
35 Correct 413 ms 78124 KB Output is correct
36 Correct 479 ms 96816 KB Output is correct
37 Correct 619 ms 96808 KB Output is correct
38 Correct 531 ms 96888 KB Output is correct
39 Correct 875 ms 94204 KB Output is correct
40 Correct 631 ms 92748 KB Output is correct
41 Correct 1216 ms 93640 KB Output is correct
42 Correct 770 ms 93980 KB Output is correct
43 Correct 635 ms 93216 KB Output is correct
44 Correct 312 ms 12188 KB Output is correct
45 Correct 178 ms 11780 KB Output is correct
46 Correct 428 ms 11804 KB Output is correct
47 Correct 178 ms 11760 KB Output is correct
48 Correct 147 ms 11724 KB Output is correct
49 Correct 647 ms 115260 KB Output is correct
50 Correct 1018 ms 115040 KB Output is correct
51 Correct 308 ms 12184 KB Output is correct
52 Correct 466 ms 11768 KB Output is correct
53 Correct 672 ms 96236 KB Output is correct
54 Correct 780 ms 94492 KB Output is correct
55 Correct 1172 ms 96296 KB Output is correct
56 Correct 1405 ms 96520 KB Output is correct
57 Correct 361 ms 12228 KB Output is correct
58 Correct 308 ms 12168 KB Output is correct
59 Correct 478 ms 11752 KB Output is correct
60 Correct 480 ms 11724 KB Output is correct
61 Correct 540 ms 114960 KB Output is correct
62 Correct 561 ms 96668 KB Output is correct
63 Correct 682 ms 95016 KB Output is correct
64 Correct 683 ms 115016 KB Output is correct
65 Correct 697 ms 96320 KB Output is correct
66 Correct 975 ms 94916 KB Output is correct
67 Correct 846 ms 114952 KB Output is correct
68 Correct 865 ms 96688 KB Output is correct
69 Correct 926 ms 95480 KB Output is correct
70 Correct 532 ms 115004 KB Output is correct
71 Correct 463 ms 96576 KB Output is correct
72 Correct 593 ms 94328 KB Output is correct
73 Correct 498 ms 115028 KB Output is correct
74 Correct 501 ms 96512 KB Output is correct
75 Correct 671 ms 97616 KB Output is correct
76 Correct 676 ms 115568 KB Output is correct
77 Correct 834 ms 115500 KB Output is correct
78 Correct 507 ms 115328 KB Output is correct
79 Correct 314 ms 12184 KB Output is correct
80 Correct 332 ms 11820 KB Output is correct
81 Correct 150 ms 11756 KB Output is correct
82 Correct 748 ms 115528 KB Output is correct
83 Correct 793 ms 116116 KB Output is correct
84 Correct 833 ms 115280 KB Output is correct
85 Correct 996 ms 118188 KB Output is correct
86 Correct 502 ms 115280 KB Output is correct
87 Correct 645 ms 115820 KB Output is correct
88 Correct 320 ms 12188 KB Output is correct
89 Correct 331 ms 12124 KB Output is correct
90 Correct 348 ms 11780 KB Output is correct
91 Correct 341 ms 11828 KB Output is correct
92 Correct 146 ms 11784 KB Output is correct
93 Correct 144 ms 11748 KB Output is correct
94 Correct 647 ms 78776 KB Output is correct
95 Correct 838 ms 98684 KB Output is correct
96 Correct 793 ms 78492 KB Output is correct
97 Correct 962 ms 99200 KB Output is correct
98 Correct 469 ms 78680 KB Output is correct
99 Correct 604 ms 96180 KB Output is correct
100 Correct 333 ms 12132 KB Output is correct
101 Correct 324 ms 12124 KB Output is correct
102 Correct 291 ms 11852 KB Output is correct
103 Correct 298 ms 11772 KB Output is correct
104 Correct 141 ms 11788 KB Output is correct
105 Correct 146 ms 11868 KB Output is correct
106 Correct 674 ms 96660 KB Output is correct
107 Correct 825 ms 96860 KB Output is correct
108 Correct 869 ms 97152 KB Output is correct
109 Correct 963 ms 94576 KB Output is correct
110 Correct 483 ms 97240 KB Output is correct
111 Correct 615 ms 95216 KB Output is correct
112 Correct 327 ms 12216 KB Output is correct
113 Correct 328 ms 12280 KB Output is correct
114 Correct 327 ms 11852 KB Output is correct
115 Correct 346 ms 11720 KB Output is correct
116 Correct 144 ms 11752 KB Output is correct
117 Correct 143 ms 11780 KB Output is correct
118 Correct 503 ms 114660 KB Output is correct
119 Correct 521 ms 96228 KB Output is correct
120 Correct 813 ms 97608 KB Output is correct
121 Correct 524 ms 114680 KB Output is correct
122 Correct 515 ms 96096 KB Output is correct
123 Correct 648 ms 96248 KB Output is correct
124 Correct 487 ms 115012 KB Output is correct
125 Correct 512 ms 96872 KB Output is correct
126 Correct 618 ms 96972 KB Output is correct