QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#263369#7528. Effective ManagementMikhail#WA 0ms3800kbC++172.1kb2023-11-24 19:37:542023-11-24 19:37:55

Judging History

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

  • [2023-11-24 19:37:55]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3800kb
  • [2023-11-24 19:37:54]
  • 提交

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'