Submission #1231132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231132		alterio	Closing Time (IOI23_closing)	C++20	75 / 100	202 ms	5188 KiB

closing

#include <bits/stdc++.h>
#include "closing.h"   

using namespace std;

#define ll long long

const int mxn = 3010;

vector<pair<ll, ll>> g[mxn];

ll dist[mxn][2];

void dfs(int node, int type) {
    queue<pair<ll, ll>> q;
    q.push({0, node});
    dist[node][type] = 0;
    while (q.size()) {
        auto top = q.front();
        q.pop();
        ll D = top.first, cur = top.second;
        for (auto x : g[cur]) {
            ll to = x.first, weight = x.second;
            ll newD = D + weight;
            if (newD < dist[to][type]) {
                dist[to][type] = newD;
                q.push({newD, to});
            }
        }
    }
}

int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
    for (int i = 0; i < N; i++) dist[i][0] = dist[i][1] = 1e15, g[i].clear();
    for (int i = 0; i < N - 1; i++) {
        g[U[i]].push_back({V[i], W[i]});
        g[V[i]].push_back({U[i], W[i]});
    }
    dfs(X, 0);
    dfs(Y, 1);
    vector<ll> v;
    for (int i = 0; i < N; i++) {
        v.push_back(min(dist[i][0], dist[i][1]));
    }
    sort(v.begin(), v.end());
    ll sum = 0, ans1 = 0;
    for (int i = 0; i < N; i++) {
        sum += v[i];
        if (sum > K) break;
        ans1++;
    }
    ll ans2 = 0;
    sum = 0;
    for (int i = 0; i < N; i++) {
        if (dist[Y][0] == dist[i][0] + dist[i][1]) {
            sum += min(dist[i][0], dist[i][1]);
            ans2++;
        }
    }
    ll MX = 2 * N + 10;
    ll dp[MX];
    for (int i = 0; i < MX; i++) dp[i] = 1e15;
    dp[ans2] = sum;
    for (int i = 0; i < N; i++) {
        ll mn = min(dist[i][0], dist[i][1]), mx = max(dist[i][0], dist[i][1]);
        if (dist[Y][0] == dist[i][0] + dist[i][1]) {
            mn = dist[Y][0] - 2 * mn, mx = 1e15;
        }
        for (int j = 2 * N; j >= 0; j--) {
            ll res = dp[j];
            if (j - 1 >= 0) res = min(res, dp[j - 1] + mn);
            if (j - 2 >= 0) res = min(res, dp[j - 2] + mx);
            dp[j] = res;
        }
    }
    ans2 = 0;
    for (int j = 2 * N; j >= 0; j--) {
        if (dp[j] <= K) {
            ans2 = j;
            break;
        }
    }
    return max(ans1, ans2);
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 9 / 9
• Subtask 6: 11 / 11
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 17