Submission #1132508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132508		SpyrosAliv	Closing Time (IOI23_closing)	C++20	0 / 100	32 ms	9028 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 max_score(int sz, int x, int y, ll l, vector<int> u, vector<int> v, vector<int> weights) {
    tree.clear();
    tree.resize(n+1);
    for (int i = 0; i < n-1; i++) {
        tree[u[i]].push_back({v[i], w[i]});
        tree[v[i]].push_back({u[i], w[i]});
    }
    n = sz;
    minX.clear();
    minX.assign(n, 0LL);
    minY.clear();
    minY.assign(n, 0LL);
    k = l;
    w = weights;
    bool line = true;
    for (int i = 0; i < n-2; i++) {
        if (v[i] != u[i] + 1) {
            line = false;
            break;
        }
    }
    if (line) return solve_line();
    else {
        dfs(x, false);
        dfs(y, true);
        vector<ll> costs;
        for (int i = 0; i < n; i++) {
            costs.push_back(minX[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(7, 0, 2, 10, {0, 0, 1, 2, 2, 5}, {1, 3, 2, 4, 5, 6}, {2, 3, 4, 2, 5, 3}) << "\n";
}*/

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 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