답안 #739710

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
739710 2023-05-11T05:31:36 Z torisasami Job Scheduling (IOI19_job) C++14
24 / 100
257 ms 34696 KB
// #define _GLIBCXX_DEBUG
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < int(n); i++)
#define per(i, n) for (int i = (n)-1; 0 <= i; i--)
#define rep2(i, l, r) for (int i = (l); i < int(r); i++)
#define per2(i, l, r) for (int i = (r)-1; int(l) <= i; i--)
#define each(e, v) for (auto& e : v)
#define MM << " " <<
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)x.size()
template <typename T> void print(const vector<T>& v, T x = 0) {
    int n = v.size();
    for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');
    if (v.empty()) cout << '\n';
}
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T> bool chmax(T& x, const T& y) {
    return (x < y) ? (x = y, true) : false;
}
template <typename T> bool chmin(T& x, const T& y) {
    return (x > y) ? (x = y, true) : false;
}
template <class T>
using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template <class T> using maxheap = std::priority_queue<T>;
template <typename T> int lb(const vector<T>& v, T x) {
    return lower_bound(begin(v), end(v), x) - begin(v);
}
template <typename T> int ub(const vector<T>& v, T x) {
    return upper_bound(begin(v), end(v), x) - begin(v);
}
template <typename T> void rearrange(vector<T>& v) {
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
}

// __int128_t gcd(__int128_t a, __int128_t b) {
//     if (a == 0)
//         return b;
//     if (b == 0)
//         return a;
//     __int128_t cnt = a % b;
//     while (cnt != 0) {
//         a = b;
//         b = cnt;
//         cnt = a % b;
//     }
//     return b;
// }

long long extGCD(long long a, long long b, long long& x, long long& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

struct UnionFind {
    vector<int> data;
    int num;

    UnionFind(int sz) {
        data.assign(sz, -1);
        num = sz;
    }

    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return (false);
        if (data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        num--;
        return (true);
    }

    int find(int k) {
        if (data[k] < 0) return (k);
        return (data[k] = find(data[k]));
    }

    int size(int k) { return (-data[find(k)]); }

    bool same(int x, int y) { return find(x) == find(y); }

    int operator[](int k) { return find(k); }
};

template <int mod> struct Mod_Int {
    int x;

    Mod_Int() : x(0) {}

    Mod_Int(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    static int get_mod() { return mod; }

    Mod_Int& operator+=(const Mod_Int& p) {
        if ((x += p.x) >= mod) x -= mod;
        return *this;
    }

    Mod_Int& operator-=(const Mod_Int& p) {
        if ((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }

    Mod_Int& operator*=(const Mod_Int& p) {
        x = (int)(1LL * x * p.x % mod);
        return *this;
    }

    Mod_Int& operator/=(const Mod_Int& p) {
        *this *= p.inverse();
        return *this;
    }

    Mod_Int& operator++() { return *this += Mod_Int(1); }

    Mod_Int operator++(int) {
        Mod_Int tmp = *this;
        ++*this;
        return tmp;
    }

    Mod_Int& operator--() { return *this -= Mod_Int(1); }

    Mod_Int operator--(int) {
        Mod_Int tmp = *this;
        --*this;
        return tmp;
    }

    Mod_Int operator-() const { return Mod_Int(-x); }

    Mod_Int operator+(const Mod_Int& p) const { return Mod_Int(*this) += p; }

    Mod_Int operator-(const Mod_Int& p) const { return Mod_Int(*this) -= p; }

    Mod_Int operator*(const Mod_Int& p) const { return Mod_Int(*this) *= p; }

    Mod_Int operator/(const Mod_Int& p) const { return Mod_Int(*this) /= p; }

    bool operator==(const Mod_Int& p) const { return x == p.x; }

    bool operator!=(const Mod_Int& p) const { return x != p.x; }

    Mod_Int inverse() const {
        assert(*this != Mod_Int(0));
        return pow(mod - 2);
    }

    Mod_Int pow(long long k) const {
        Mod_Int now = *this, ret = 1;
        for (; k > 0; k >>= 1, now *= now) {
            if (k & 1) ret *= now;
        }
        return ret;
    }

    friend ostream& operator<<(ostream& os, const Mod_Int& p) {
        return os << p.x;
    }

    friend istream& operator>>(istream& is, Mod_Int& p) {
        long long a;
        is >> a;
        p = Mod_Int<mod>(a);
        return is;
    }
};

ll mpow2(ll x, ll n, ll mod) {
    ll ans = 1;
    x %= mod;
    while (n != 0) {
        if (n & 1) ans = ans * x % mod;
        x = x * x % mod;
        n = n >> 1;
    }
    ans %= mod;
    return ans;
}

template <typename T> T modinv(T a, const T& m) {
    T b = m, u = 1, v = 0;
    while (b > 0) {
        T t = a / b;
        swap(a -= t * b, b);
        swap(u -= t * v, v);
    }
    return u >= 0 ? u % m : (m - (-u) % m) % m;
}

ll divide_int(ll a, ll b) {
    if (b < 0) a = -a, b = -b;
    return (a >= 0 ? a / b : (a - b + 1) / b);
}

// const int MOD = 1000000007;
const int MOD = 998244353;
using mint = Mod_Int<MOD>;

mint mpow(mint x, ll n) {
    bool rev = n < 0;
    n = abs(n);
    mint ans = 1;
    while (n != 0) {
        if (n & 1) ans *= x;
        x *= x;
        n = n >> 1;
    }
    return (rev ? ans.inverse() : ans);
}

// ----- library -------
template <typename T>
struct Tree_Optimal_Order {
    using F = function<T(T, T)>;
    using C = function<bool(T, T)>;

    int n;
    const F f;
    const C comp;
    vector<vector<int>> g;
    vector<int> par, h, l, to;
    vector<T> val;

    // comp(i, j) == true  <=>  pref[i] < pref[j]
    Tree_Optimal_Order(int n, const F f, const C comp) : n(n), f(f), comp(comp), g(n), par(n), h(n), l(n), to(n), val(n) {}

    void add_edge(int u, int v) {
        g[u].emplace_back(v), g[v].emplace_back(u);
    }

    void dfs(int k) {
        for (auto &e: g[k]) {
            if (e != par[k])
                par[e] = k, dfs(e);
        }
    }
    
    int head(int k) {
        if (h[k] == -1)
            return k;
        return h[k] = head(h[k]);
    }

    void merge(int k) {
        int p = head(par[k]);
        h[k] = p, to[l[p]] = k, l[p] = l[k], val[p] = f(val[p], val[k]);
    }
    
    vector<int> solve(vector<T> v, int root = 0) {
        val = move(v);
        fill(par.begin(), par.end(), -1);
        dfs(root);
        fill(h.begin(), h.end(), -1);
        iota(l.begin(), l.end(), 0);
        vector<bool> vis(n, false);
        priority_queue<int, vector<int>, function<bool(int, int)>> que(
            [&](int i, int j){return comp(val[i], val[j]);}
        );
        for (int i = 0; i < n; i++) if (i != root) que.push(i);
        while (que.size()) {
            int now = que.top();
            que.pop();
            if (vis[now]) continue;
            vis[now] = true;
            merge(now);
            if (head(now) != root)
                que.push(head(now));
        }
        vector<int> ret{root};
        for (int i = 0; i < n - 1; i++)
            ret.emplace_back(to[ret.back()]);
        return ret;
    }
};

ll scheduling_cost(vector<int> p, vector<int> u, vector<int> d) {
    int n = sz(p);
    auto f = [](pii a, pii b){return make_pair(a.first + b.first, a.second + b.second);};
    auto comp = [](pii a, pii b){return a.first * b.second < a.second * b.first;};
    Tree_Optimal_Order<pii> g(n, f, comp);
    rep2(i, 1, n) g.add_edge(p[i], i);
    vector<pii> val;
    rep(i, n) val.eb(u[i], d[i]);
    auto ret = g.solve(val);
    ll ans = 0, s = 0;
    rep(i, n) s += d[ret[i]], ans += s * u[ret[i]];
    return ans;
}
// ----- library -------
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 56 ms 8824 KB Output is correct
6 Correct 117 ms 17304 KB Output is correct
7 Correct 177 ms 26192 KB Output is correct
8 Correct 244 ms 34564 KB Output is correct
9 Correct 236 ms 34628 KB Output is correct
10 Correct 234 ms 34632 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 247 ms 34696 KB Output is correct
13 Correct 219 ms 34680 KB Output is correct
14 Correct 211 ms 34584 KB Output is correct
15 Correct 217 ms 34596 KB Output is correct
16 Correct 205 ms 34556 KB Output is correct
17 Correct 238 ms 34568 KB Output is correct
18 Correct 238 ms 34592 KB Output is correct
19 Correct 220 ms 34580 KB Output is correct
20 Correct 145 ms 34592 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 160 ms 27440 KB Output is correct
5 Correct 145 ms 27292 KB Output is correct
6 Correct 141 ms 27392 KB Output is correct
7 Correct 150 ms 27384 KB Output is correct
8 Correct 146 ms 27384 KB Output is correct
9 Correct 145 ms 27288 KB Output is correct
10 Correct 147 ms 27420 KB Output is correct
11 Correct 148 ms 27324 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 7 ms 1748 KB Output is correct
6 Correct 151 ms 27912 KB Output is correct
7 Correct 155 ms 28028 KB Output is correct
8 Correct 161 ms 28032 KB Output is correct
9 Correct 146 ms 27912 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 6 ms 1488 KB Output is correct
13 Correct 6 ms 1748 KB Output is correct
14 Correct 162 ms 27948 KB Output is correct
15 Correct 153 ms 27880 KB Output is correct
16 Correct 155 ms 27940 KB Output is correct
17 Correct 145 ms 27944 KB Output is correct
18 Correct 166 ms 27932 KB Output is correct
19 Correct 163 ms 27892 KB Output is correct
20 Correct 165 ms 27940 KB Output is correct
21 Correct 162 ms 27944 KB Output is correct
22 Correct 160 ms 27908 KB Output is correct
23 Correct 163 ms 27940 KB Output is correct
24 Correct 159 ms 27936 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 257 ms 31332 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 56 ms 8824 KB Output is correct
6 Correct 117 ms 17304 KB Output is correct
7 Correct 177 ms 26192 KB Output is correct
8 Correct 244 ms 34564 KB Output is correct
9 Correct 236 ms 34628 KB Output is correct
10 Correct 234 ms 34632 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 247 ms 34696 KB Output is correct
13 Correct 219 ms 34680 KB Output is correct
14 Correct 211 ms 34584 KB Output is correct
15 Correct 217 ms 34596 KB Output is correct
16 Correct 205 ms 34556 KB Output is correct
17 Correct 238 ms 34568 KB Output is correct
18 Correct 238 ms 34592 KB Output is correct
19 Correct 220 ms 34580 KB Output is correct
20 Correct 145 ms 34592 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 160 ms 27440 KB Output is correct
25 Correct 145 ms 27292 KB Output is correct
26 Correct 141 ms 27392 KB Output is correct
27 Correct 150 ms 27384 KB Output is correct
28 Correct 146 ms 27384 KB Output is correct
29 Correct 145 ms 27288 KB Output is correct
30 Correct 147 ms 27420 KB Output is correct
31 Correct 148 ms 27324 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 300 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 7 ms 1748 KB Output is correct
37 Correct 151 ms 27912 KB Output is correct
38 Correct 155 ms 28028 KB Output is correct
39 Correct 161 ms 28032 KB Output is correct
40 Correct 146 ms 27912 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 1 ms 468 KB Output is correct
43 Correct 6 ms 1488 KB Output is correct
44 Correct 6 ms 1748 KB Output is correct
45 Correct 162 ms 27948 KB Output is correct
46 Correct 153 ms 27880 KB Output is correct
47 Correct 155 ms 27940 KB Output is correct
48 Correct 145 ms 27944 KB Output is correct
49 Correct 166 ms 27932 KB Output is correct
50 Correct 163 ms 27892 KB Output is correct
51 Correct 165 ms 27940 KB Output is correct
52 Correct 162 ms 27944 KB Output is correct
53 Correct 160 ms 27908 KB Output is correct
54 Correct 163 ms 27940 KB Output is correct
55 Correct 159 ms 27936 KB Output is correct
56 Correct 0 ms 212 KB Output is correct
57 Incorrect 257 ms 31332 KB Output isn't correct
58 Halted 0 ms 0 KB -