oj.uz

Submission #1081856

# Submission time Handle Problem Language Result Execution time Memory
1081856 2024-08-30T12:04:22 Z Thunnus Bitaro’s Party (JOI18_bitaro) C++17
100 / 100
 609 ms 286408 KB 
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size() 

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	const int SZ = 100;
	int n, m, q, a, b;
	cin >> n >> m >> q;
	vvi adj(n), radj(n);
	for(int i = 0; i < m; i++){
		cin >> a >> b;
		adj[--a].emplace_back(--b);
		radj[b].emplace_back(a);
	}

	vector<vector<pii>> bestSZ(n);
	vi starting(n, -1);
	for(int v = 0; v < n; v++){ // Duplicates are the issue
		vi from;
		bestSZ[v].emplace_back(0, v);
		for(int &u : radj[v]){
			for(pii &d : bestSZ[u]){
				if(starting[d.se] == -1){
					from.emplace_back(d.se);
					starting[d.se] = d.fi + 1;
				}
				else{
					starting[d.se] = max(starting[d.se], d.fi + 1);
				}
			}
		}
		for(int &u : from){
			bestSZ[v].emplace_back(starting[u], u);
		}
		sort(bestSZ[v].begin(), bestSZ[v].end(), greater<pii>());
		while(sz(bestSZ[v]) > SZ){
			bestSZ[v].pop_back();
		}

		for(int &u : from){
			starting[u] = -1;
		}
	}

	vb can(n, true);
	while(q--){
		int t, y, ans = -1;
		cin >> t >> y;
		t--;
		vi yi(y);
		for(int i = 0; i < y; i++){
			cin >> yi[i];
			can[--yi[i]] = false;
		}

		if(y >= SZ){
			vi dp(t + 1, -1);
			dp[t] = 0;
			for(int v = t; v >= 0; v--){
				if(dp[v] == -1) continue;
				if(can[v]) ans = max(ans, dp[v]);
				for(int &u : radj[v]){
					dp[u] = max(dp[u], dp[v] + 1);
				}
			}
		}
		else{
			for(pii &p : bestSZ[t]){
				if(can[p.se]){
					ans = p.fi;
					break;
				}
			}
		}
		
		for(int i = 0; i < y; i++){
			can[yi[i]] = true;
		}
		cout << ans << "\n";
	}
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 3 ms 1372 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 3 ms 2396 KB Output is correct
12 Correct 5 ms 2140 KB Output is correct
13 Correct 4 ms 2408 KB Output is correct
14 Correct 2 ms 1556 KB Output is correct
15 Correct 3 ms 1492 KB Output is correct
16 Correct 3 ms 1884 KB Output is correct
17 Correct 5 ms 1884 KB Output is correct
18 Correct 3 ms 1624 KB Output is correct
19 Correct 3 ms 1884 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 3 ms 1372 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 3 ms 2396 KB Output is correct
12 Correct 5 ms 2140 KB Output is correct
13 Correct 4 ms 2408 KB Output is correct
14 Correct 2 ms 1556 KB Output is correct
15 Correct 3 ms 1492 KB Output is correct
16 Correct 3 ms 1884 KB Output is correct
17 Correct 5 ms 1884 KB Output is correct
18 Correct 3 ms 1624 KB Output is correct
19 Correct 3 ms 1884 KB Output is correct
20 Correct 55 ms 8532 KB Output is correct
21 Correct 55 ms 8612 KB Output is correct
22 Correct 49 ms 8520 KB Output is correct
23 Correct 57 ms 8532 KB Output is correct
24 Correct 541 ms 225740 KB Output is correct
25 Correct 547 ms 217684 KB Output is correct
26 Correct 546 ms 216900 KB Output is correct
27 Correct 345 ms 221980 KB Output is correct
28 Correct 337 ms 222044 KB Output is correct
29 Correct 327 ms 222192 KB Output is correct
30 Correct 312 ms 220752 KB Output is correct
31 Correct 399 ms 257108 KB Output is correct
32 Correct 308 ms 220756 KB Output is correct
33 Correct 272 ms 148932 KB Output is correct
34 Correct 447 ms 207444 KB Output is correct
35 Correct 265 ms 148564 KB Output is correct
36 Correct 295 ms 183124 KB Output is correct
37 Correct 455 ms 226388 KB Output is correct
38 Correct 280 ms 183124 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 3 ms 1372 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 3 ms 2396 KB Output is correct
12 Correct 5 ms 2140 KB Output is correct
13 Correct 4 ms 2408 KB Output is correct
14 Correct 2 ms 1556 KB Output is correct
15 Correct 3 ms 1492 KB Output is correct
16 Correct 3 ms 1884 KB Output is correct
17 Correct 5 ms 1884 KB Output is correct
18 Correct 3 ms 1624 KB Output is correct
19 Correct 3 ms 1884 KB Output is correct
20 Correct 55 ms 8532 KB Output is correct
21 Correct 55 ms 8612 KB Output is correct
22 Correct 49 ms 8520 KB Output is correct
23 Correct 57 ms 8532 KB Output is correct
24 Correct 541 ms 225740 KB Output is correct
25 Correct 547 ms 217684 KB Output is correct
26 Correct 546 ms 216900 KB Output is correct
27 Correct 345 ms 221980 KB Output is correct
28 Correct 337 ms 222044 KB Output is correct
29 Correct 327 ms 222192 KB Output is correct
30 Correct 312 ms 220752 KB Output is correct
31 Correct 399 ms 257108 KB Output is correct
32 Correct 308 ms 220756 KB Output is correct
33 Correct 272 ms 148932 KB Output is correct
34 Correct 447 ms 207444 KB Output is correct
35 Correct 265 ms 148564 KB Output is correct
36 Correct 295 ms 183124 KB Output is correct
37 Correct 455 ms 226388 KB Output is correct
38 Correct 280 ms 183124 KB Output is correct
39 Correct 528 ms 228948 KB Output is correct
40 Correct 479 ms 220240 KB Output is correct
41 Correct 514 ms 223720 KB Output is correct
42 Correct 491 ms 222020 KB Output is correct
43 Correct 486 ms 225260 KB Output is correct
44 Correct 63 ms 9812 KB Output is correct
45 Correct 53 ms 9088 KB Output is correct
46 Correct 95 ms 9036 KB Output is correct
47 Correct 54 ms 8792 KB Output is correct
48 Correct 47 ms 8472 KB Output is correct
49 Correct 342 ms 222292 KB Output is correct
50 Correct 606 ms 222620 KB Output is correct
51 Correct 62 ms 9812 KB Output is correct
52 Correct 96 ms 8940 KB Output is correct
53 Correct 304 ms 182596 KB Output is correct
54 Correct 475 ms 224956 KB Output is correct
55 Correct 469 ms 182764 KB Output is correct
56 Correct 575 ms 232184 KB Output is correct
57 Correct 62 ms 9808 KB Output is correct
58 Correct 61 ms 9552 KB Output is correct
59 Correct 98 ms 8984 KB Output is correct
60 Correct 95 ms 8788 KB Output is correct
61 Correct 359 ms 221908 KB Output is correct
62 Correct 325 ms 183948 KB Output is correct
63 Correct 453 ms 223764 KB Output is correct
64 Correct 476 ms 222536 KB Output is correct
65 Correct 384 ms 182932 KB Output is correct
66 Correct 520 ms 226828 KB Output is correct
67 Correct 585 ms 222272 KB Output is correct
68 Correct 442 ms 183708 KB Output is correct
69 Correct 543 ms 227748 KB Output is correct
70 Correct 323 ms 222560 KB Output is correct
71 Correct 278 ms 183336 KB Output is correct
72 Correct 452 ms 226900 KB Output is correct
73 Correct 326 ms 222436 KB Output is correct
74 Correct 294 ms 183140 KB Output is correct
75 Correct 452 ms 231836 KB Output is correct
76 Correct 319 ms 222804 KB Output is correct
77 Correct 609 ms 222632 KB Output is correct
78 Correct 317 ms 222204 KB Output is correct
79 Correct 64 ms 9784 KB Output is correct
80 Correct 88 ms 9044 KB Output is correct
81 Correct 51 ms 8788 KB Output is correct
82 Correct 319 ms 221960 KB Output is correct
83 Correct 442 ms 264644 KB Output is correct
84 Correct 552 ms 221616 KB Output is correct
85 Correct 573 ms 286408 KB Output is correct
86 Correct 300 ms 221092 KB Output is correct
87 Correct 411 ms 263808 KB Output is correct
88 Correct 64 ms 9808 KB Output is correct
89 Correct 67 ms 9812 KB Output is correct
90 Correct 98 ms 9044 KB Output is correct
91 Correct 106 ms 9060 KB Output is correct
92 Correct 48 ms 8636 KB Output is correct
93 Correct 48 ms 8528 KB Output is correct
94 Correct 279 ms 150604 KB Output is correct
95 Correct 479 ms 221484 KB Output is correct
96 Correct 420 ms 149576 KB Output is correct
97 Correct 556 ms 223428 KB Output is correct
98 Correct 256 ms 149880 KB Output is correct
99 Correct 416 ms 214944 KB Output is correct
100 Correct 62 ms 9812 KB Output is correct
101 Correct 63 ms 9936 KB Output is correct
102 Correct 82 ms 8984 KB Output is correct
103 Correct 79 ms 9044 KB Output is correct
104 Correct 46 ms 8628 KB Output is correct
105 Correct 45 ms 8664 KB Output is correct
106 Correct 303 ms 183124 KB Output is correct
107 Correct 558 ms 235692 KB Output is correct
108 Correct 432 ms 183744 KB Output is correct
109 Correct 513 ms 219136 KB Output is correct
110 Correct 309 ms 184408 KB Output is correct
111 Correct 443 ms 229124 KB Output is correct
112 Correct 62 ms 9976 KB Output is correct
113 Correct 62 ms 9972 KB Output is correct
114 Correct 89 ms 8876 KB Output is correct
115 Correct 89 ms 9040 KB Output is correct
116 Correct 45 ms 8532 KB Output is correct
117 Correct 47 ms 8532 KB Output is correct
118 Correct 303 ms 221012 KB Output is correct
119 Correct 272 ms 182600 KB Output is correct
120 Correct 470 ms 237140 KB Output is correct
121 Correct 300 ms 221088 KB Output is correct
122 Correct 276 ms 181840 KB Output is correct
123 Correct 469 ms 235600 KB Output is correct
124 Correct 305 ms 221152 KB Output is correct
125 Correct 289 ms 182868 KB Output is correct
126 Correct 445 ms 229064 KB Output is correct