QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#227098 | #7528. Effective Management | Piashy# | WA | 26ms | 24072kb | C++20 | 2.2kb | 2023-10-26 22:06:08 | 2023-10-26 22:06:08 |
Judging History
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'