Submission #154861

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
154861	2019-09-25T12:01:46 Z	pink_bittern	Job Scheduling (IOI19_job)	C++14	Compilation error	0 ms	0 KB

job

#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;

vector <ll> V[maxn];

pll ANS[maxn];

bool BAD[maxn];

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

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

void dfs(ll v, ll p){
    ll q;
    vector <ll> S;
    for (q = 0; q < V[v].size(); q++){
        if (V[v][q] == p){
            continue;
        }
        S.pb(V[v][q]);
        dfs(V[v][q], v);
    }
    pll cur = mp(D[v], U[v]);
    sort(S.begin(), S.end(), cmp1);
    ll j = S.size(), t = D[v];
    for (q = 0; q < S.size(); q++){
        ll v1 = S[q];
        if (!cmp(ANS[v1], cur)){
            j = q;
            break;
        }
        else{
            cur.first += ANS[v1].first;
            cur.second += ANS[v1].second;
            BAD[v1] = 1;
        }
    }
    ans -= (cur.first - t) * (U[v]);
    for (q = 0; q < j; q++){
        ll v1 = S[q];
        t += ANS[v1].first;
        ans -= (cur.first - t) * (ANS[v1].second);
    }
    ANS[v] = cur;
//    cout << v << " CUR " << cur.first << " " << cur.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]);
        }
    }
    if (is_bamboo){
        ll t = 0;
        for (q = 0; q < n; q++){
            t += d[q];
            ans += t * u[q];
        }
        return ans;
    }
    dfs(0, 0);
    vector <ll> ALL;
    for (q = 0; q < n; q++){
        ALL.pb(q);
    }
    sort(ALL.begin(), ALL.end(), cmp1);
    ll t = 0;
    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;
}

int main(){
    ll q, w, e, t, a, b, c;
    cin >> n;
    vector <int> p(n), u(n), d(n);
    for (q = 0; q < n; q++){
        cin >> p[q];
    }
    for (q = 0; q < n; q++){
        cin >> u[q];
    }
    for (q = 0; q < n; q++){
        cin >> d[q];
    }
    cout << scheduling_cost(p, u, d);
    return 0;
}

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:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (q = 0; q < V[v].size(); q++){
                 ~~^~~~~~~~~~~~~
job.cpp:58:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (q = 0; q < S.size(); q++){
                 ~~^~~~~~~~~~
job.cpp: In function 'll scheduling_cost(std::vector<int>, std::vector<int>, std::vector<int>)':
job.cpp:111:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (q = 0; q < ALL.size(); q++){
                 ~~^~~~~~~~~~~~
job.cpp:83:11: warning: unused variable 'w' [-Wunused-variable]
     ll q, w, e, a, b;
           ^
job.cpp:83:14: warning: unused variable 'e' [-Wunused-variable]
     ll q, w, e, a, b;
              ^
job.cpp:83:17: warning: unused variable 'a' [-Wunused-variable]
     ll q, w, e, a, b;
                 ^
job.cpp:83:20: warning: unused variable 'b' [-Wunused-variable]
     ll q, w, e, a, b;
                    ^
job.cpp: In function 'int main()':
job.cpp:122:11: warning: unused variable 'w' [-Wunused-variable]
     ll q, w, e, t, a, b, c;
           ^
job.cpp:122:14: warning: unused variable 'e' [-Wunused-variable]
     ll q, w, e, t, a, b, c;
              ^
job.cpp:122:17: warning: unused variable 't' [-Wunused-variable]
     ll q, w, e, t, a, b, c;
                 ^
job.cpp:122:20: warning: unused variable 'a' [-Wunused-variable]
     ll q, w, e, t, a, b, c;
                    ^
job.cpp:122:23: warning: unused variable 'b' [-Wunused-variable]
     ll q, w, e, t, a, b, c;
                       ^
job.cpp:122:26: warning: unused variable 'c' [-Wunused-variable]
     ll q, w, e, t, a, b, c;
                          ^
/tmp/cclupN2y.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccAPFEJ5.o:job.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status