oj.uz

Submission #739655

# Submission time Handle Problem Language Result Execution time Memory
739655 2023-05-11T00:08:40 Z Markomafko972 Bitaro’s Party (JOI18_bitaro) C++14
100 / 100
 1171 ms 218280 KB 
#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);

int n, m, q, a, b, tren, kol;
vector<int> v[100005];
int sq = 233;
int bio[100005];
int z[100005];
int dp[100005];
vector<pii> w[100005];
int pos[100005];

int dfs(int x) {
	if (dp[x] != -1) return dp[x];
	
	dp[x] = -1e9;
	if (bio[x] == 0) dp[x] = 0;
	for (int i = 0; i < (int)v[x].size(); i++) {
		dp[x] = max(dp[x], dfs(v[x][i])+1);
	}
	
	return dp[x];
}

void natrag(int x) {
	if (dp[x] == -1) return;
	
	dp[x] = -1;
	for (int i = 0; i < (int)v[x].size(); i++) natrag(v[x][i]);
}

int main () {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m >> q;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		v[b].push_back(a);
	}
	
	for (int i = 1; i <= n; i++) {
		
		//cout << i << endl;
		
		while ((int)w[i].size() < sq) {
			int da = 0;
			for (int j = 0; j < (int)v[i].size(); j++) {
				while (pos[v[i][j]] < (int)w[v[i][j]].size() && bio[w[v[i][j]][pos[v[i][j]]].X]) pos[v[i][j]]++;
				
				if (pos[v[i][j]] < (int)w[v[i][j]].size()) {
					da = 1;
				}
			}
			if (da == 0) break;
			
			int maxi = 0, cvor = 0, slj = 0;
			for (int j = 0; j < (int)v[i].size(); j++) {
				if (pos[v[i][j]] < (int)w[v[i][j]].size() && w[v[i][j]][pos[v[i][j]]].Y+1 > maxi && bio[w[v[i][j]][pos[v[i][j]]].X] == 0) {
					maxi = w[v[i][j]][pos[v[i][j]]].Y+1;
					cvor = w[v[i][j]][pos[v[i][j]]].X;
					slj = v[i][j];
				}
			}
			
			w[i].push_back({cvor, maxi});
			pos[slj]++;
			bio[cvor] = 1;
			//cout << cvor << " " << maxi << endl;
		}
		
		if ((int)w[i].size() < sq) w[i].push_back({i, 0});
		
		for (int j = 0; j < (int)v[i].size(); j++) pos[v[i][j]] = 0;
		for (int j = 0; j < (int)w[i].size(); j++) bio[w[i][j].X] = 0;
	}
	
	
	//for (int i = 0; i < w[6].size(); i++) cout << w[6][i].X << " " << w[6][i].Y << endl;
	//cout << endl;
	
	for (int i = 0; i < q; i++) {
		cin >> tren >> kol;
		for (int j = 0; j < kol; j++) {
			cin >> z[j];
			bio[z[j]] = 1;
		}
		
		if (kol >= sq) {
			memset(dp, -1, sizeof dp);
			int rj = dfs(tren);
			if (rj < 0) cout << "-1\n";
			else cout << rj << "\n";
			//natrag(tren);
		}
		else {
			int da = 0;
			for (int j = 0; j < (int)w[tren].size(); j++) {
				if (bio[w[tren][j].X] == 0) {
					cout << w[tren][j].Y << "\n";
					da = 1;
					break;
				}
			}
			
			if (da == 0) cout << "-1\n";
		}
		
		for (int j = 0; j < kol; j++) bio[z[j]] = 0;
	}

	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 6 ms 5844 KB Output is correct
6 Correct 5 ms 5844 KB Output is correct
7 Correct 5 ms 5808 KB Output is correct
8 Correct 8 ms 7252 KB Output is correct
9 Correct 9 ms 7252 KB Output is correct
10 Correct 8 ms 7348 KB Output is correct
11 Correct 8 ms 7124 KB Output is correct
12 Correct 6 ms 6580 KB Output is correct
13 Correct 8 ms 7124 KB Output is correct
14 Correct 7 ms 6444 KB Output is correct
15 Correct 5 ms 5972 KB Output is correct
16 Correct 7 ms 6444 KB Output is correct
17 Correct 8 ms 6740 KB Output is correct
18 Correct 7 ms 6296 KB Output is correct
19 Correct 8 ms 6740 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 6 ms 5844 KB Output is correct
6 Correct 5 ms 5844 KB Output is correct
7 Correct 5 ms 5808 KB Output is correct
8 Correct 8 ms 7252 KB Output is correct
9 Correct 9 ms 7252 KB Output is correct
10 Correct 8 ms 7348 KB Output is correct
11 Correct 8 ms 7124 KB Output is correct
12 Correct 6 ms 6580 KB Output is correct
13 Correct 8 ms 7124 KB Output is correct
14 Correct 7 ms 6444 KB Output is correct
15 Correct 5 ms 5972 KB Output is correct
16 Correct 7 ms 6444 KB Output is correct
17 Correct 8 ms 6740 KB Output is correct
18 Correct 7 ms 6296 KB Output is correct
19 Correct 8 ms 6740 KB Output is correct
20 Correct 387 ms 8848 KB Output is correct
21 Correct 401 ms 8940 KB Output is correct
22 Correct 396 ms 8964 KB Output is correct
23 Correct 422 ms 9012 KB Output is correct
24 Correct 532 ms 151716 KB Output is correct
25 Correct 551 ms 156092 KB Output is correct
26 Correct 551 ms 156260 KB Output is correct
27 Correct 645 ms 214088 KB Output is correct
28 Correct 649 ms 214196 KB Output is correct
29 Correct 651 ms 214956 KB Output is correct
30 Correct 676 ms 211656 KB Output is correct
31 Correct 666 ms 206224 KB Output is correct
32 Correct 657 ms 211468 KB Output is correct
33 Correct 446 ms 133448 KB Output is correct
34 Correct 403 ms 114856 KB Output is correct
35 Correct 458 ms 132556 KB Output is correct
36 Correct 540 ms 172624 KB Output is correct
37 Correct 547 ms 160484 KB Output is correct
38 Correct 540 ms 173172 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 6 ms 5844 KB Output is correct
6 Correct 5 ms 5844 KB Output is correct
7 Correct 5 ms 5808 KB Output is correct
8 Correct 8 ms 7252 KB Output is correct
9 Correct 9 ms 7252 KB Output is correct
10 Correct 8 ms 7348 KB Output is correct
11 Correct 8 ms 7124 KB Output is correct
12 Correct 6 ms 6580 KB Output is correct
13 Correct 8 ms 7124 KB Output is correct
14 Correct 7 ms 6444 KB Output is correct
15 Correct 5 ms 5972 KB Output is correct
16 Correct 7 ms 6444 KB Output is correct
17 Correct 8 ms 6740 KB Output is correct
18 Correct 7 ms 6296 KB Output is correct
19 Correct 8 ms 6740 KB Output is correct
20 Correct 387 ms 8848 KB Output is correct
21 Correct 401 ms 8940 KB Output is correct
22 Correct 396 ms 8964 KB Output is correct
23 Correct 422 ms 9012 KB Output is correct
24 Correct 532 ms 151716 KB Output is correct
25 Correct 551 ms 156092 KB Output is correct
26 Correct 551 ms 156260 KB Output is correct
27 Correct 645 ms 214088 KB Output is correct
28 Correct 649 ms 214196 KB Output is correct
29 Correct 651 ms 214956 KB Output is correct
30 Correct 676 ms 211656 KB Output is correct
31 Correct 666 ms 206224 KB Output is correct
32 Correct 657 ms 211468 KB Output is correct
33 Correct 446 ms 133448 KB Output is correct
34 Correct 403 ms 114856 KB Output is correct
35 Correct 458 ms 132556 KB Output is correct
36 Correct 540 ms 172624 KB Output is correct
37 Correct 547 ms 160484 KB Output is correct
38 Correct 540 ms 173172 KB Output is correct
39 Correct 573 ms 152744 KB Output is correct
40 Correct 567 ms 153572 KB Output is correct
41 Correct 542 ms 154036 KB Output is correct
42 Correct 542 ms 154488 KB Output is correct
43 Correct 555 ms 153456 KB Output is correct
44 Correct 416 ms 8636 KB Output is correct
45 Correct 405 ms 8292 KB Output is correct
46 Correct 408 ms 8412 KB Output is correct
47 Correct 423 ms 8648 KB Output is correct
48 Correct 405 ms 8592 KB Output is correct
49 Correct 677 ms 211036 KB Output is correct
50 Correct 653 ms 210428 KB Output is correct
51 Correct 430 ms 8532 KB Output is correct
52 Correct 404 ms 8240 KB Output is correct
53 Correct 580 ms 171900 KB Output is correct
54 Correct 586 ms 163232 KB Output is correct
55 Correct 540 ms 174144 KB Output is correct
56 Correct 532 ms 162792 KB Output is correct
57 Correct 429 ms 10684 KB Output is correct
58 Correct 418 ms 10724 KB Output is correct
59 Correct 400 ms 9804 KB Output is correct
60 Correct 421 ms 9804 KB Output is correct
61 Correct 814 ms 217980 KB Output is correct
62 Correct 649 ms 175168 KB Output is correct
63 Correct 615 ms 162108 KB Output is correct
64 Correct 1171 ms 218088 KB Output is correct
65 Correct 835 ms 174548 KB Output is correct
66 Correct 711 ms 163352 KB Output is correct
67 Correct 664 ms 216156 KB Output is correct
68 Correct 546 ms 175176 KB Output is correct
69 Correct 540 ms 161280 KB Output is correct
70 Correct 677 ms 217752 KB Output is correct
71 Correct 570 ms 175240 KB Output is correct
72 Correct 553 ms 162688 KB Output is correct
73 Correct 718 ms 218108 KB Output is correct
74 Correct 605 ms 175036 KB Output is correct
75 Correct 552 ms 162636 KB Output is correct
76 Correct 699 ms 214888 KB Output is correct
77 Correct 648 ms 213580 KB Output is correct
78 Correct 678 ms 218280 KB Output is correct
79 Correct 415 ms 10792 KB Output is correct
80 Correct 393 ms 9960 KB Output is correct
81 Correct 401 ms 9884 KB Output is correct
82 Correct 695 ms 214944 KB Output is correct
83 Correct 716 ms 209380 KB Output is correct
84 Correct 642 ms 213580 KB Output is correct
85 Correct 671 ms 208384 KB Output is correct
86 Correct 659 ms 214676 KB Output is correct
87 Correct 674 ms 209016 KB Output is correct
88 Correct 419 ms 10828 KB Output is correct
89 Correct 427 ms 10784 KB Output is correct
90 Correct 403 ms 9940 KB Output is correct
91 Correct 401 ms 9932 KB Output is correct
92 Correct 396 ms 9988 KB Output is correct
93 Correct 390 ms 9980 KB Output is correct
94 Correct 483 ms 136916 KB Output is correct
95 Correct 415 ms 117536 KB Output is correct
96 Correct 452 ms 135140 KB Output is correct
97 Correct 386 ms 118860 KB Output is correct
98 Correct 460 ms 135884 KB Output is correct
99 Correct 401 ms 118400 KB Output is correct
100 Correct 429 ms 10824 KB Output is correct
101 Correct 436 ms 10916 KB Output is correct
102 Correct 408 ms 9968 KB Output is correct
103 Correct 425 ms 10032 KB Output is correct
104 Correct 406 ms 10060 KB Output is correct
105 Correct 427 ms 9992 KB Output is correct
106 Correct 579 ms 175372 KB Output is correct
107 Correct 568 ms 163732 KB Output is correct
108 Correct 546 ms 175152 KB Output is correct
109 Correct 543 ms 162252 KB Output is correct
110 Correct 556 ms 175820 KB Output is correct
111 Correct 553 ms 163404 KB Output is correct
112 Correct 432 ms 10956 KB Output is correct
113 Correct 411 ms 10956 KB Output is correct
114 Correct 395 ms 10024 KB Output is correct
115 Correct 390 ms 9924 KB Output is correct
116 Correct 413 ms 9904 KB Output is correct
117 Correct 387 ms 9844 KB Output is correct
118 Correct 640 ms 213196 KB Output is correct
119 Correct 535 ms 174944 KB Output is correct
120 Correct 535 ms 162068 KB Output is correct
121 Correct 652 ms 213008 KB Output is correct
122 Correct 567 ms 174240 KB Output is correct
123 Correct 532 ms 161780 KB Output is correct
124 Correct 641 ms 212884 KB Output is correct
125 Correct 536 ms 175164 KB Output is correct
126 Correct 531 ms 161424 KB Output is correct