oj.uz

Submission #322041

# Submission time Handle Problem Language Result Execution time Memory
322041 2020-11-13T23:59:36 Z fivefourthreeone Job Scheduling (IOI19_job) C++17
12 / 100
 247 ms 16996 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(auto i=(a);i<(b); ++i)
#define uwu(i,a, b) for(auto i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<ttgl, null_type,less<ttgl>, rb_tree_tag,tree_order_statistics_node_update>*/
 
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 62;
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = atan(1);
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 200001;
vector<int> adj[mxN];
int p[mxN];
int n;
int dsu[mxN];
bool done[mxN];
bool bad[mxN];
bool cmp(array<int, 3> a, array<int, 3> b) {
    if(a[0]*b[1]==a[1]*b[0]) {
        return a[2] < b[2];
    }
    return a[0]*b[1] > a[1]*b[0];
}
int find(int a) {
    return a==dsu[a] ? a : dsu[a] = find(dsu[a]);
}
bool merge(int a, int b) {
    a = find(a);
    b = find(b);
    if(a==b)return false;
    dsu[b] = a;
    bad[b] = true;
    return true;
}
ll scheduling_cost(vector<int> par, vector<int> u, vector<int> d) {
    n = par.size();
    iota(dsu, dsu+n, 0);
    priority_queue<array<int, 3>, vector<array<int, 3>>, decltype(&cmp)> pq(cmp);
    owo(i, 0, n) {
        pq.push({d[i], u[i], i});
    }
    ll res = 0;
    ll curr = 0;
    while(!pq.empty()) {
        auto[t, cst, id] = pq.top();
        pq.pop();
        //cout<<t<<" "<<cst<<" "<<id<<endl;
        if(tie(t, cst)!=tie(d[id], u[id]) || done[id] || bad[id])continue;
        if(par[id]==-1 || done[find(par[id])]) {
            curr+=t;
            res+=1LL*cst*curr;
            done[id] = true;
            continue;
        }
        int nxt = find(par[id]);
        res-=1LL*t*u[nxt];
        u[nxt]+=cst;
        d[nxt]+=t;
        merge(nxt, id);
        pq.push({d[nxt], u[nxt], nxt});
    }
    return res;
}/*
vector<int> PAR, U, D;
int N;
int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>N;
    PAR.resize(N);
    U.resize(N);
    D.resize(N);
    owo(i, 0, N) {
        cin>>PAR[i];
    }
    owo(i, 0, N) {
        cin>>U[i];
    }
    owo(i, 0, N) {
        cin>>D[i];
    }
    cout<<scheduling_cost(PAR, U, D);
    return 0;
}*/

Compilation message

job.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
job.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 47 ms 8096 KB Output is correct
6 Correct 99 ms 10984 KB Output is correct
7 Correct 155 ms 14692 KB Output is correct
8 Correct 226 ms 16868 KB Output is correct
9 Correct 241 ms 16868 KB Output is correct
10 Correct 227 ms 16996 KB Output is correct
11 Correct 4 ms 4972 KB Output is correct
12 Correct 229 ms 16884 KB Output is correct
13 Correct 207 ms 16868 KB Output is correct
14 Correct 196 ms 16868 KB Output is correct
15 Correct 182 ms 16900 KB Output is correct
16 Correct 187 ms 16868 KB Output is correct
17 Correct 223 ms 16868 KB Output is correct
18 Correct 245 ms 16868 KB Output is correct
19 Correct 178 ms 16996 KB Output is correct
20 Correct 127 ms 16868 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 142 ms 13668 KB Output is correct
5 Correct 139 ms 13680 KB Output is correct
6 Correct 146 ms 13796 KB Output is correct
7 Correct 148 ms 13796 KB Output is correct
8 Correct 144 ms 13668 KB Output is correct
9 Correct 140 ms 13668 KB Output is correct
10 Correct 138 ms 13668 KB Output is correct
11 Correct 137 ms 13796 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Incorrect 9 ms 5612 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4972 KB Output is correct
2 Incorrect 247 ms 13668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 4972 KB Output is correct
7 Correct 4 ms 4972 KB Output is correct
8 Incorrect 4 ms 4972 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 47 ms 8096 KB Output is correct
6 Correct 99 ms 10984 KB Output is correct
7 Correct 155 ms 14692 KB Output is correct
8 Correct 226 ms 16868 KB Output is correct
9 Correct 241 ms 16868 KB Output is correct
10 Correct 227 ms 16996 KB Output is correct
11 Correct 4 ms 4972 KB Output is correct
12 Correct 229 ms 16884 KB Output is correct
13 Correct 207 ms 16868 KB Output is correct
14 Correct 196 ms 16868 KB Output is correct
15 Correct 182 ms 16900 KB Output is correct
16 Correct 187 ms 16868 KB Output is correct
17 Correct 223 ms 16868 KB Output is correct
18 Correct 245 ms 16868 KB Output is correct
19 Correct 178 ms 16996 KB Output is correct
20 Correct 127 ms 16868 KB Output is correct
21 Correct 3 ms 4972 KB Output is correct
22 Correct 4 ms 4972 KB Output is correct
23 Correct 4 ms 4972 KB Output is correct
24 Correct 142 ms 13668 KB Output is correct
25 Correct 139 ms 13680 KB Output is correct
26 Correct 146 ms 13796 KB Output is correct
27 Correct 148 ms 13796 KB Output is correct
28 Correct 144 ms 13668 KB Output is correct
29 Correct 140 ms 13668 KB Output is correct
30 Correct 138 ms 13668 KB Output is correct
31 Correct 137 ms 13796 KB Output is correct
32 Correct 4 ms 4972 KB Output is correct
33 Correct 4 ms 4972 KB Output is correct
34 Correct 4 ms 4972 KB Output is correct
35 Correct 4 ms 5100 KB Output is correct
36 Incorrect 9 ms 5612 KB Output isn't correct
37 Halted 0 ms 0 KB -