QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#263369 | #7528. Effective Management | Mikhail# | WA | 0ms | 3800kb | C++17 | 2.1kb | 2023-11-24 19:37:54 | 2023-11-24 19:37:55 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define cheat ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define cyes cout<<"Yes"<<endl
#define cno cout<<"No"<<endl
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fe first
#define se second
using namespace std;
const ll inf = 1e18;
struct detail {
ll cost, time;
int id;
};
bool cmp(const detail &a, const detail &b) {
if(a.cost * b.time == a.time * b.cost) {
return a.id < b.id;
}
return a.cost * b.time > a.time * b.cost;
}
int main(){
int n;
cin >> n;
vector <ll> cost(n);
vector <ll> time(n);
for(ll&x : cost) {
cin >> x;
}
for(ll&x: time) {
cin >> x;
}
set <pair <ll, int>> st;
vector <ll> dist = time; //max_time
vector <vector <int>> gr(n);
vector <vector <int>> par(n);
for(int u = 0; u < n; u++) {
int k;
cin >> k;
if(k == 0) {
st.insert({time[u], u});
dist[u] = time[u];
} else {
for(int i = 0; i < k; i++) {
int to;
cin >> to;
to--;
gr[u].push_back({to});
par[to].push_back(u);
}
}
}
while(!st.empty()) {
auto e = *st.begin();
st.erase(e);
int v = e.second;
for(int to: par[v]) {
if(dist[v] > dist[to]) {
st.erase({dist[to], to});
dist[to] = dist[v];
st.insert({dist[to], to});
}
}
}
vector <detail> rat(n);
for(int i = 0; i < n; i++) {
rat[i] = {cost[i], dist[i], i};
}
sort(rat.begin(), rat.end(), cmp);
/*for(auto a: rat) {
cout << a.cost << ' ' << a.time << ' ' << a.id << endl;
}
cout << endl; */
cout << rat[0].id + 1 << '\n';
for(int i = 1; i < n; i++) {
if(rat[i - 1].cost * rat[i].time != rat[i - 1].time * rat[i].cost) {
break;
}
cout << rat[i].id + 1 << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3800kb
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: 3588kb
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: 3732kb
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: 3472kb
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: 3544kb
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: -100
Wrong Answer
time: 0ms
memory: 3752kb
input:
5 1 2 8 5 2 1 7 9 9 4 1 3 2 3 5 2 4 5 0 0
output:
1
result:
wrong answer 1st numbers differ - expected: '3', found: '1'