QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#227098#7528. Effective ManagementPiashy#WA 26ms24072kbC++202.2kb2023-10-26 22:06:082023-10-26 22:06:08

Judging History

你现在查看的是最新测评结果

  • [2023-10-26 22:06:08]
  • 评测
  • 测评结果:WA
  • 用时:26ms
  • 内存:24072kb
  • [2023-10-26 22:06:08]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

#define ll long long
#define ull unsigned long long
#define ld long double
#define sz(a) (int) a.size()

const int inf = (int)1e9;
const ll linf = (ll)2e18;

const ll mod = (ll)1e9 + 7ll;

void dfs(int v, vector<vector<int>>& graph, vector<bool>& used, vector<int>& top_sort) {
	used[v] = true;
	for (int u : graph[v]) {
		if (!used[u]) dfs(u, graph, used, top_sort);
	}
	top_sort.push_back(v);
}

void solve() {
	int n; cin >> n;
	vector<ll> c(n);
	vector<ll> t(n);

	vector<vector<int>> graph(n);
	vector<vector<ll>> z(n);
	for (int i = 0; i < n; ++i) cin >> c[i];
	for (int i = 0; i < n; ++i) cin >> t[i];

	for (int i = 0; i < n; ++i) {
		int m; cin >> m;
		for (int j = 0; j < m; ++j) {
			int v; cin >> v;
			graph[--v].push_back(i);
			z[i].push_back(v);
		}
	}

	vector<bool> used(n, false);
	vector<int> top_sort;

	for (int i = 0; i < n; ++i) {
		if (!used[i]) dfs(i, graph, used, top_sort);
	}

	reverse(top_sort.begin(), top_sort.end());

	vector<int> ans;

	pair<ll, ll> p = { 0, 1 };
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < sz(z[i]); ++j) {
			t[i] = max(t[i], t[z[i][j]]);
		}

		if (p.first * t[i] < p.second * c[i]) {
			p = { c[i], t[i] };
		}
	}

	for (int i = 0; i < n; ++i) {
		if (p.first * t[i] == p.second * c[i]) ans.push_back(i + 1);
	}
	for (auto el : ans) cout << el << "\n";
}
	

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	//freopen("test.in", "r", stdin);
	//freopen("test.in", "w", stdout);
	//cout << fixed << setprecision(7);

	//clock_t start = clock();

	int tet = 1;
	//cin >> tet;
	while (tet--) {
		solve();
	}

	//clock_t end = clock();
	//ld seconds = (ld)(end - start) / CLOCKS_PER_SEC;
	//cout << seconds << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3820kb

input:

6
1 2 4 5 4 6
1 3 2 2 3 2
0
0
1 1
2 2 3
1 1
2 5 4

output:

3
6

result:

ok 2 number(s): "3 6"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

5
10 9 5 4 1
4 6 2 3 1
1 2
1 3
1 4
1 5
0

output:

1
3

result:

ok 2 number(s): "1 3"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

6
2 4 6 8 10 12
1 2 3 4 5 6
0
0
0
0
0
0

output:

1
2
3
4
5
6

result:

ok 6 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

3
999999999 1000000000 999999998
999999998 999999999 999999997
0
0
0

output:

3

result:

ok 1 number(s): "3"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

5
7 10 1 9 6
7 5 6 1 3
1 3
0
0
1 5
0

output:

4

result:

ok 1 number(s): "4"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

5
1 2 8 5 2
1 7 9 9 4
1 3
2 3 5
2 4 5
0
0

output:

3

result:

ok 1 number(s): "3"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

5
7 6 3 5 1
6 9 3 10 10
1 4
0
2 4 1
0
3 1 4 3

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

5
6 1 6 9 7
10 1 9 10 6
0
0
0
3 5 3 2
1 3

output:

2

result:

ok 1 number(s): "2"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

20
73 58 33 82 74 66 25 67 12 68 65 17 93 20 73 66 38 5 75 31
30 48 72 18 74 96 76 15 4 33 29 4 77 85 48 82 30 54 28 15
16 11 7 10 12 9 19 6 3 18 14 20 4 2 17 13 15
1 13
11 9 19 13 6 18 4 17 7 14 2 20
6 14 20 19 2 18 13
17 12 19 10 6 2 18 9 1 13 15 3 20 14 7 4 17 11
8 18 20 7 4 14 19 13 2
7 18 4 14 ...

output:

13

result:

ok 1 number(s): "13"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

5
7 9 7 2 10
6 5 8 8 1
0
0
0
0
0

output:

5

result:

ok 1 number(s): "5"

Test #11:

score: 0
Accepted
time: 2ms
memory: 4184kb

input:

1000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok 1000 numbers

Test #12:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

10
3 3 6 12 9 6 6 6 12 9
2 2 4 8 6 4 4 4 8 6
0
0
0
0
0
0
0
0
0
0

output:

1
2
3
4
5
6
7
8
9
10

result:

ok 10 numbers

Test #13:

score: 0
Accepted
time: 1ms
memory: 3676kb

input:

1000
999999998 999999998 999999998 999999998 999999997 999999998 999999996 999999996 999999998 999999998 999999996 999999997 999999997 999999996 999999997 999999996 999999998 999999996 999999998 999999996 999999999 999999996 999999997 999999997 999999997 999999996 999999997 999999998 999999996 99999...

output:

21
31
33
41
52
55
56
70
73
78
86
87
92
94
96
97
101
108
116
124
126
131
135
149
150
152
154
155
157
158
159
162
167
169
170
173
175
180
181
184
185
186
189
191
192
195
197
204
207
211
212
218
236
237
242
249
255
259
268
270
272
275
279
286
288
290
291
293
303
304
309
312
314
319
325
328
337
347
350
...

result:

ok 250 numbers

Test #14:

score: 0
Accepted
time: 1ms
memory: 3924kb

input:

1000
999999999 999999998 999999999 999999998 1000000000 999999998 500000000 500000000 499999999 999999999 999999998 500000000 499999999 999999999 999999998 999999999 999999999 999999998 999999999 500000000 499999999 999999998 999999999 999999998 999999999 499999999 500000000 500000000 999999999 4999...

output:

2
4
6
9
11
13
15
18
21
22
24
26
30
31
33
37
38
39
43
53
56
59
60
64
67
68
78
80
83
91
95
97
101
104
107
109
110
111
114
115
119
126
128
129
130
131
137
138
139
140
142
143
144
145
147
148
149
150
153
154
155
156
157
159
160
162
167
168
171
179
184
185
189
190
192
195
197
200
201
202
204
205
207
208
...

result:

ok 412 numbers

Test #15:

score: 0
Accepted
time: 22ms
memory: 24072kb

input:

100000
549754 665095 953607 740223 783230 929059 754985 955883 851448 616686 506945 371717 240711 257263 235454 937268 417102 669196 714839 601216 365749 139857 335172 759449 816678 379440 527491 941265 446416 581116 175892 833949 191848 877037 760254 681239 832227 535647 920840 22335 950270 216466 ...

output:

2

result:

ok 1 number(s): "2"

Test #16:

score: -100
Wrong Answer
time: 26ms
memory: 16316kb

input:

100000
689096 903050 277980 888409 868489 971675 914696 566610 310739 215200 333485 708143 617714 319199 723553 320623 395110 773615 323884 177509 245794 526973 633548 709813 172557 987401 910707 358556 459330 920167 362565 292710 437650 455104 137244 681207 15358 492689 101510 547717 662912 704617 ...

output:

572

result:

wrong answer 1st numbers differ - expected: '99993', found: '572'