제출 #1042294

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1042294		Lobo	Jobs (BOI24_jobs)	C++17	43 / 100	2081 ms	18260 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18 + 10;
const int inf1 = 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const int maxn = 3e5+10;

int n, s, x[maxn], p[maxn], sm[maxn], pf[maxn], ds[maxn], dsz[maxn];

priority_queue<pair<int,int>> pq;

int find(int u) {
    if(ds[u] == u) return u;
    return ds[u] = find(ds[u]);
}

void join(int u, int v) {
    u = find(u);
    v = find(v);

    if(dsz[u] < dsz[v]) swap(u,v);
    dsz[u]+= dsz[v];
    ds[v] = u;
    return;
}

void solve() {
    cin >> n >> s;
    for(int i = 1; i <= n; i++) {
        cin >> x[i] >> p[i];
        sm[i] = x[i];
        pf[i] = x[i];
        ds[i] = i;
        dsz[i] = 1;
    }
    sm[0] = s;
    pf[0] = 0;
    ds[0] = 0;
    dsz[0] = 1;

    for(int it = 1; it <= n; it++) {
        for(int i = 1; i <= n; i++) {
            int u = find(p[i]);
            int v = find(i);
            if(u == v) continue;
            if(sm[v] >= 0 && -min(pf[u],sm[u]+pf[v]) <= sm[find(0)]) {
                // cout << it << " " << i << " " << p[i] << " " << -min(pf[u],sm[u]+pf[v]) << endl;
                int newsm = sm[u]+sm[v];
                int newpf = min(pf[u],sm[u]+pf[v]);
                join(u,v);
                v = find(v);
                sm[v] = newsm;
                pf[v] = newpf;
            }
        }
    }

    int st = find(0);
    cout << sm[st]-s << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    #ifndef ONLINE_JUDGE
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    #endif

    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

• Subtask 1: 0 / 11
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 29 / 29
• Subtask 5: 0 / 31