oj.uz

답안 #211348

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
211348 2020-03-20T07:28:24 Z 2qbingxuan Job Scheduling (IOI19_job) C++14
0 / 100
 3000 ms 15336 KB 
//#include "job.h"
#include <bits/stdc++.h>
using namespace std;

long long scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
    int n = p.size();
    struct node {
        long long u, d;
        int id;
        bool operator<(node p)const{
            return u*p.d < d*p.u;
        }
    };
    long long ans = 0;
    vector<int> pa(n);
    iota(pa.begin(), pa.end(), 0);
    function<int(int)> anc = [&](int x){
        return x==pa[x] ? x : pa[x]=anc(pa[x]);
    };
    auto add = [&](int a, int i) {
        ans -= d[i] * u[a];
        d[a] += d[i];
        u[a] += u[i];
    };
    priority_queue<node> pq;
    for(int i = 0; i < n; i++) {
        pq.push({u[i],d[i],i});
    }
    while(pq.size() > 1) {
        node x;
        do x=pq.top(), pq.pop(); while(pq.size() && x.u!=u[x.id] || x.d!=d[x.id]);
        //if(pq.empty()) break;
        int i = x.id;
        if(p[i] == -1) continue;
        int a = anc(p[i]);
        pa[i] = a;
        add(a, i);
        pq.push({u[a],d[a],a});
    }
    ans += pq.top().u * pq.top().d;
    return ans;
}

Compilation message

job.cpp: In function 'long long int scheduling_cost(std::vector<int>, std::vector<int>, std::vector<int>)':
job.cpp:31:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         do x=pq.top(), pq.pop(); while(pq.size() && x.u!=u[x.id] || x.d!=d[x.id]);

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Incorrect 4 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 4 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Execution timed out 3054 ms 15336 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3049 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -