oj.uz

Submission #155240

# Submission time Handle Problem Language Result Execution time Memory
155240 2019-09-27T08:44:14 Z pink_bittern Job Scheduling (IOI19_job) C++14
0 / 100
 17 ms 14584 KB 
#include <bits/stdc++.h>
#include <complex>
#define pb push_back
#define pll pair <ll, ll>
#define MOMI using namespace std;
#define mp make_pair
#define pyshnapyshnakaa ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#pragma optimize("TKACHENKO-GORYACHENKO")
#pragma GCC optimize("O3")

//#pragma GCC optimize("unroll-loops")

typedef long long ll;

typedef long double ld;

using namespace std;

const ll maxn = 2e5 + 100;

ll n, m, k;

ll P[maxn];

ll U[maxn];

ll D[maxn];

ll ans = 0;

bool BAD[maxn];

vector <ll> V[maxn];

pll ANS[maxn];

bool cmp(pll a, pll b){
    return a.first * b.second < b.first * a.second;
}

struct cmp1{
    bool operator ()(ll a, ll b){
        return cmp(ANS[a], ANS[b]);
    }
};

bool cmp2(ll a, ll b){
    return cmp(ANS[a], ANS[b]);
}

ll I[maxn];

set <ll, cmp1> S[maxn];

void dfs(ll v, ll p){
    ll q;
    ll mx = 0;
    for (q = 0; q < V[v].size(); q++){
        if (V[v][q] == p){
            continue;
        }
        dfs(V[v][q], v);
        ll i = I[V[v][q]];
        if (S[i].size() < mx){
            mx = S[i].size();
            I[v] = i;
        }
    }
    for (q = 0; q < V[v].size(); q++){
        if (V[v][q] == p){
            continue;
        }
        if (I[V[v][q]] == I[v]){
            continue;
        }
        ll i = I[V[v][q]];
        for (auto el : S[i]){
            S[I[v]].insert(el);
        }
    }
    ANS[v] = mp(D[v], U[v]);
    S[I[v]].insert(v);
    vector <ll> merged;
    ll t = D[v], st = D[v];
    while (1){
        ll i = *(S[I[v]].begin());
        if (cmp2(i, v)){
            merged.pb(i);
            st += ANS[i].first;
            S[I[v]].erase(S[I[v]].begin());
            ANS[v].first += ANS[i].first;
            ANS[v].second += ANS[i].second;
        }
        else{
            break;
        }
    }
    ans -= (st - t) * (U[v]);
//    cout << "DANS " << (st - t) * (U[v]) << " " << st << " " << t << " " << v << endl;
    for (q = 0; q < merged.size(); q++){
        ll i = merged[q];
        BAD[i] = 1;
        t += ANS[i].first;
        ans -= ANS[i].second * (st - t);
//        cout << "DANS1 " << (st - t) * (ANS[i].second) << endl;
    }
}

ll scheduling_cost(vector <int> p, vector <int> u, vector <int> d){
    n = p.size();
    bool is_bamboo = 1;
    ll q, w, e, a, b;
    for (q = 0; q < n; q++){
        P[q] = p[q];
        U[q] = u[q];
        D[q] = d[q];
        if (p[q] != q - 1){
            is_bamboo = 0;
        }
        if (p[q] != -1){
            V[p[q]].pb(q);
            V[q].pb(p[q]);
        }
    }
    dfs(0, 0);
    vector <ll> ALL;
    for (q = 0; q < n; q++){
        ALL.pb(q);
    }
    sort(ALL.begin(), ALL.end(), cmp2);
    ll t = 0;
//    cout << "ANS B4 " << ans << endl;
    for (q = 0; q < ALL.size(); q++){
        if (BAD[ALL[q]]){
            continue;
        }
        t += ANS[ALL[q]].first;
        ans += ANS[ALL[q]].second * t;
    }
    return ans;
}

Compilation message

job.cpp:8:0: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
 #pragma optimize("TKACHENKO-GORYACHENKO")
 
job.cpp: In function 'void dfs(ll, ll)':
job.cpp:58:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (q = 0; q < V[v].size(); q++){
                 ~~^~~~~~~~~~~~~
job.cpp:64:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (S[i].size() < mx){
             ~~~~~~~~~~~~^~~~
job.cpp:69:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (q = 0; q < V[v].size(); q++){
                 ~~^~~~~~~~~~~~~
job.cpp:100:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (q = 0; q < merged.size(); q++){
                 ~~^~~~~~~~~~~~~~~
job.cpp: In function 'll scheduling_cost(std::vector<int>, std::vector<int>, std::vector<int>)':
job.cpp:133:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (q = 0; q < ALL.size(); q++){
                 ~~^~~~~~~~~~~~
job.cpp:111:10: warning: variable 'is_bamboo' set but not used [-Wunused-but-set-variable]
     bool is_bamboo = 1;
          ^~~~~~~~~
job.cpp:112:11: warning: unused variable 'w' [-Wunused-variable]
     ll q, w, e, a, b;
           ^
job.cpp:112:14: warning: unused variable 'e' [-Wunused-variable]
     ll q, w, e, a, b;
              ^
job.cpp:112:17: warning: unused variable 'a' [-Wunused-variable]
     ll q, w, e, a, b;
                 ^
job.cpp:112:20: warning: unused variable 'b' [-Wunused-variable]
     ll q, w, e, a, b;
                    ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Incorrect 14 ms 14456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14584 KB Output is correct
2 Incorrect 14 ms 14528 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 14456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 14456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14460 KB Output is correct
2 Incorrect 17 ms 14456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Incorrect 14 ms 14456 KB Output isn't correct
3 Halted 0 ms 0 KB -