Submission #1072276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072276		sammyuri	Closing Time (IOI23_closing)	C++17	43 / 100	953 ms	146888 KiB

closing

#include "closing.h"

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3005;
typedef long long ll;
const ll INF = 4e18;

int n;
int x, y; ll k;
ll dp[MAXN][2 * MAXN];
ll mindist[MAXN], maxdist[MAXN];
vector<int> curpath;
bool forced[MAXN];
vector<pair<int, ll>> adj[200005];
priority_queue<ll> pq;

void dfs1(int node, int parent, ll curdist) {
    pq.push(-curdist);
    for (auto a : adj[node])
        if (a.first != parent)
            dfs1(a.first, node, a.second + curdist);
}
void dfs2(int node, int parent, ll curdist) {
    mindist[node] = min(mindist[node], curdist);
    maxdist[node] = max(maxdist[node], curdist);
    for (auto a : adj[node])
        if (a.first != parent)
            dfs2(a.first, node, a.second + curdist);
}
bool dfs3(int node, int parent) {
    curpath.push_back(node);
    if (node == y) {
        for (auto a : curpath)
            forced[a] = true;
        return true;
    }
    for (auto a : adj[node])
        if (a.first != parent)
            if (dfs3(a.first, node))
                return true;
    curpath.pop_back();
    return false;
}

int solve_brute() {
    while (pq.size())
        pq.pop();
    dfs1(x, -1, 0); dfs1(y, -1, 0);
    int ans = 0;
    ll cost = 0;
    while (cost <= k && pq.size()) {
        ll cur = -pq.top(); pq.pop();
        if (cost + cur <= k)
            ans ++, cost += cur;
        else break;
    }
    return ans;
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    memset(forced, false, sizeof(forced));
    n = N;
    x = X; y = Y; k = K;
    for (int i = 0; i < n - 1; i ++) {
        int a, b; ll c;
        a = U[i]; b = V[i]; c = W[i];
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    if (N > MAXN) {
        int ans = solve_brute();
        for (int i = 0; i < n; i ++)
            adj[i].clear();
        return ans;
    }
    for (int i = 0; i <= N; i ++)
        for (int j = 0; j <= 2 * N; j ++)
            dp[i][j] = INF;
    for (int i = 0; i < n; i ++)
        maxdist[i] = 0, mindist[i] = INF;
    curpath.clear();
    dfs2(x, -1, 0); dfs2(y, -1, 0);
    dfs3(x, -1);
    dp[0][0] = 0;
    for (int i = 1; i <= n; i ++) {
        // do not take
        if (!forced[i])
            for (int j = 0; j <= 2 * n; j ++)
                dp[i][j] = min(dp[i][j], dp[i - 1][j]);
        // take once
        for (int j = 1; j <= 2 * n; j ++) {
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + mindist[i - 1]);
        }
        // take twice
        for (int j = 2; j <= 2 * n; j ++) {
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 2] + maxdist[i - 1]);
        }
    }
    int best = 0;
    for (int j = 0; j <= 2 * n; j ++)
        if (dp[n][j] <= k)
            best = max(best, j);
    best = max(best, solve_brute());
        for (int i = 0; i < n; i ++)
            adj[i].clear();
    return best;
}

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