Submission #154846

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
154846	2019-09-25T10:23:23 Z	pink_bittern	Job Scheduling (IOI19_job)	C++17	19 / 100	215 ms	41320 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;

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();
    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] != -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(), 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;
}

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:100:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (q = 0; q < ALL.size(); q++){
                 ~~^~~~~~~~~~~~
job.cpp:82:11: warning: unused variable 'w' [-Wunused-variable]
     ll q, w, e, a, b;
           ^
job.cpp:82:14: warning: unused variable 'e' [-Wunused-variable]
     ll q, w, e, a, b;
              ^
job.cpp:82:17: warning: unused variable 'a' [-Wunused-variable]
     ll q, w, e, a, b;
                 ^
job.cpp:82: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	6 ms	4984 KB	Output is correct
2	Incorrect	7 ms	5112 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	4984 KB	Output is correct
2	Correct	6 ms	4984 KB	Output is correct
3	Correct	7 ms	4984 KB	Output is correct
4	Correct	173 ms	30980 KB	Output is correct
5	Correct	179 ms	31012 KB	Output is correct
6	Correct	173 ms	30948 KB	Output is correct
7	Correct	173 ms	30916 KB	Output is correct
8	Correct	173 ms	30772 KB	Output is correct
9	Correct	172 ms	30912 KB	Output is correct
10	Correct	173 ms	30916 KB	Output is correct
11	Correct	172 ms	30788 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	4984 KB	Output is correct
2	Correct	7 ms	5112 KB	Output is correct
3	Correct	7 ms	5112 KB	Output is correct
4	Correct	7 ms	5240 KB	Output is correct
5	Correct	14 ms	6444 KB	Output is correct
6	Correct	193 ms	31720 KB	Output is correct
7	Correct	192 ms	31676 KB	Output is correct
8	Correct	190 ms	31428 KB	Output is correct
9	Correct	189 ms	31572 KB	Output is correct
10	Correct	6 ms	4988 KB	Output is correct
11	Correct	8 ms	5188 KB	Output is correct
12	Correct	15 ms	6272 KB	Output is correct
13	Correct	15 ms	6444 KB	Output is correct
14	Correct	215 ms	31668 KB	Output is correct
15	Correct	191 ms	31428 KB	Output is correct
16	Correct	190 ms	31556 KB	Output is correct
17	Correct	190 ms	31684 KB	Output is correct
18	Correct	191 ms	31376 KB	Output is correct
19	Correct	191 ms	31520 KB	Output is correct
20	Correct	193 ms	31572 KB	Output is correct
21	Correct	199 ms	31468 KB	Output is correct
22	Correct	206 ms	31544 KB	Output is correct
23	Correct	189 ms	31428 KB	Output is correct
24	Correct	213 ms	31428 KB	Output is correct