Submission #1271470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271470		antonn	Closing Time (IOI23_closing)	C++20	29 / 100	1094 ms	28416 KiB

closing

#include <bits/stdc++.h>

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 3000 + 7;

vector<pi> g[N];
vi stk, path;

void dfs(int u, int t, int p = -1) {
    stk.push_back(u);
    if (u == t) path = stk;
    for (auto [v, w] : g[u]) {
        if (v == p) continue;
        dfs(v, t, u);
    }
    stk.pop_back();
}

bool spec[N];
vi down;

void collect(int u, int p = -1) {
    down.push_back(u);
    for (auto [v, w] : g[u]) {
        if (!spec[v] && v != p) {
            collect(v, u);
        }
    }
}

ll dp[N][N][3];

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 - 1; ++i) {
        g[U[i]].push_back({V[i], W[i]});
        g[V[i]].push_back({U[i], W[i]});
    }
    path.clear();
    dfs(x, y);
    for (auto x : path) spec[x] = 1;
 
    auto get_dist = [&](int u) {
        vector<ll> dist(n, -1);
        queue<int> q;
        q.push(u);
        dist[u] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto [v, w] : g[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + w;
                    q.push(v);
                }
            }
        }
        return dist;
    };
    vector<ll> dx = get_dist(x), dy = get_dist(y);
    
    vector<vi> v;
    for (auto x : path) {
        down.clear();
        collect(x);
        v.push_back(down);
    }
    vector<vector<vector<ll>>> mn(4, vector<vector<ll>>(v.size()));
    for (int x = 0; x < 4; ++x) {
        auto f = [&](int node, int x) {
            ll val = 0;
            if (x == 1) {
                val = dx[node];
            } else if (x == 3) {
                val = max(dx[node], dy[node]);
            } else if (x == 2) {
                val = dy[node];
            }
            return val;
        };
        for (int i = 0; i < v.size(); ++i) {
            mn[x][i].assign(2 * n + 1, 1e18);
            sort(v[i].begin(), v[i].end(), [&](int a, int b) { return f(a, x) < f(b, x); });
            vector<vector<vector<ll>>> dp(v[i].size(), vector<vector<ll>>(2 * n + 1, vector<ll>(4, 1e18)));
            dp[0][__builtin_popcount(x)][x] = f(v[i][0], x);
            for (int j = 1; j < v[i].size(); ++j) {
                int node = v[i][j]; 
                for (int sum = 0; sum <= 2 * n; ++sum) {
                    for (int s = 0; s < 4; ++s) {
                        for (int ns = 0; ns <= 4; ++ns) {
                            if ((ns & s) == ns && sum >= __builtin_popcount(ns)) {
                                ckmin(dp[j][sum][ns], dp[j - 1][sum - __builtin_popcount(ns)][s] + f(node, ns)); 
                            }
                        }
                    }
                }
            }
            for (int j = 0; j <= 2 * n; ++j) {
                mn[x][i][j] = 1e18;
                for (int s = 0; s < 4; ++s) {
                    ckmin(mn[x][i][j], dp[v[i].size() - 1][j][s]);
                }
            }
        }
    }
    int ans = 0;
    for (int mid : {0, 2}) {
        for (int i = 0; i <= path.size(); ++i) {
            for (int j = 0; j <= 2 * n; ++j) {
                for (int s = 0; s < 3; ++s) {
                    dp[i][j][s] = 1e18;
                }
            }
        }
        dp[0][0][0] = dp[0][0][1] = dp[0][0][2] = 0;
        for (int i = 1; i <= path.size(); ++i) {
            for (int j = 0; j <= 2 * n; ++j) {
                for (int s = 0; s < 3; ++s) {
                    int val = 0;
                    if (s == 0) {
                        val = 1;
                    } else if (s == 2) {
                        val = 2;
                    } else {
                        if (mid == 0) val = 0;
                        else val = 3;
                    }
                    for (int k = 0; k <= j; ++k) {
                        for (int ls = 0; ls <= s; ++ls) {
                            ckmin(dp[i][j][s], dp[i - 1][j - k][ls] + mn[val][i - 1][k]); 
                        }
                    }
                }
            }
        }
        for (int i = 0; i <= 2 * n; ++i) {
            for (int s = 0; s < 3; ++s) {
                if (dp[path.size()][i][s] <= k) {
                    ckmax(ans, i);
                }
            }
        }
    }
    for (int i = 0; i <= n; ++i) {
        g[i].clear();
        spec[i] = 0;
    }
    return ans;
}

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