Submission #1132516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132516		SpyrosAliv	Closing Time (IOI23_closing)	C++20	29 / 100	1091 ms	31968 KiB

closing

// linear network
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int n, a, b;
ll k; 
vector<int> w;
vector<ll> minX, minY;
vector<vector<pair<int, int>>> tree;

int solve_line() {
    return -1;
}

void dfs(int node, bool a, int par = -1, ll dep = 0LL) {
    if (!a) minX[node] = dep;
    else minY[node] = dep;
    for (auto [next, c]: tree[node]) {
        if (next == par) continue;
        dfs(next, a, node, dep + c);
    }
}

int solve_line(int x, int y) {
    int currS = 0;
    for (int i = x+1; i < n; i++) {
        minX[i] = minX[i-1] + w[i - 1];
    }
    for (int i = x-1; i >= 0; i--) {
        minX[i] = minX[i+1] + w[i];
    }
    for (int i = y+1; i < n; i++) {
        minY[i] = minY[i-1] + w[i - 1];
    }
    for (int i = y-1; i >= 0; i--) {
        minY[i] = minY[i+1] + w[i];
    }
    vector<ll> minBoth(n, 0);
    vector<ll> f, s;
    for (int i = 0; i < n; i++) {
        minBoth[i] = max(minX[i], minY[i]);
    }
    f = minX;
    s = minY;
    for (int i = 1; i < n; i++) {
        minX[i] = minX[i-1] + minX[i];
        minY[i] = minY[i-1] + minY[i];
        minBoth[i] = minBoth[i-1] + minBoth[i];
    }
    int maxAns = 0;
    for (int l = 0; l <= y; l++) {
        for (int r = max(x, l); r < n; r++) { // (l, r) included in both
            int ans = (r - l + 1) * 2;
            ll cost = minBoth[r];
            if (l > 0) cost -= minBoth[l-1];
            if (y > r) {
                cost += minY[y] - minY[r];
                ans += (y - r);
            }
            if (l > x) {
                cost += minX[l-1];
                if (x > 0) cost -= minX[x-1];
                ans += (l - x);
            }
            if (cost > k) continue;
            int a = min(l-1, x-1), b = max(y+1, r+1);
            while (cost <= k && (a >= 0 || b < n)) {
                int nxt = 0;
                if (a < 0) {
                    nxt = minY[b];
                    if (b > 0) nxt -= minY[b-1];
                    b++;
                }
                else if (b >= n) {
                    nxt = minX[a];
                    if (a > 0) nxt -= minX[a-1];
                    a--;
                }
                else {
                    int opt1 = minY[b], opt2 = minX[a];
                    if (a > 0) opt2 -= minX[a-1];
                    if (b > 0) opt1 -= minY[b-1];
                    if (opt2 <= opt1) {
                        a--;
                        nxt = opt2;
                    }
                    else {
                        b++;
                        nxt = opt1;
                    }
                }
                if (nxt + cost > k) break;
                cost += nxt;
                ans++;
            }
            maxAns = max(maxAns, ans);
        }
    }
    int ans = 0;
    vector<ll> sec;
    for (int i = 0; i < n; i++) {
        sec.push_back(min(f[i], s[i]));
    }
    sort(sec.begin(), sec.end());
    for (auto cr: sec) {
        if (cr <= k) {
            k -= cr;
            ans++;
        }
    }
    maxAns = max(maxAns, ans);
    return maxAns;
}

int max_score(int sz, int x, int y, ll l, vector<int> u, vector<int> v, vector<int> weights) {
    n = sz;
    tree.clear();
    tree.resize(n);
    k = l;
    w = weights;
    for (int i = 0; i < n-1; i++) {
        //int xx = u[i];
        tree[u[i]].push_back({v[i], w[i]});
        tree[v[i]].push_back({u[i], w[i]});
    }
    minX.clear();
    minX.assign(n, 0LL);
    minY.clear();
    minY.assign(n, 0LL);
    
    bool line = true;
    for (int i = 0; i < n-1; i++) {
        if (v[i] != u[i] + 1) {
            line = false;
            break;
        }
    }
    if (line) return solve_line(x, y);
    else {
        dfs(x, false);
        dfs(y, true);
        vector<ll> costs;
        for (int i = 0; i < n; i++) {
            costs.push_back(min(minX[i], minY[i]));
            //costs.push_back(minY[i]);
        }
        sort(costs.begin(), costs.end());
        int ans = 0;
        int p = (int)costs.size();
        for (int i = 0; i < p; i++) {
            ll x = costs[i];
            if (k >= x) {
                ans++;
                k -= x;
            }
            else break;
        }
        return ans;
    }
}
/*
int main() {
    cout << max_score(6, 1, 3, 5, {0, 1, 2, 3, 4}, {1, 2, 3, 4, 5}, {10, 1, 1, 1, 1}) << "\n";
}*/

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