Submission #1033194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033194		TAhmed33	Closing Time (IOI23_closing)	C++17	100 / 100	573 ms	69968 KiB

closing

#include "closing.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, x, y; ll k;
const int MAXN = 2e5 + 25;
vector <pair <ll, ll>> adj[MAXN];
ll dist[MAXN][2], f[MAXN], g[MAXN];
vector <int> cur, path;
void add_edge (int x, int y, int z) {
    adj[x].push_back({y, z});
    adj[y].push_back({x, z});
}
void dfs (int pos, int par, ll d, int c) {
    dist[pos][c] = d;
    for (auto j : adj[pos]) {
        if (j.first != par) {
            dfs(j.first, pos, d + j.second, c);
        }
    }
}
bool dfs2 (int pos, int par, int c) {
    cur.push_back(pos);
    if (pos == c) {
        path = cur;
        return 1;
    }
    for (auto j : adj[pos]) {
        if (j.first != par) {
            if (dfs2(j.first, pos, c)) {
                return 1;
            }
        }
    }
    cur.pop_back();
    return 0;
}
int solve1 () {
    vector <ll> zz;
    for (int i = 1; i <= n; i++) {
        zz.push_back(f[i]);
        zz.push_back(g[i]);
    }
    sort(zz.begin(), zz.end());
    for (int i = 1; i < 2 * n; i++) zz[i] += zz[i - 1];
    int ans1 = upper_bound(zz.begin(), zz.end(), k) - zz.begin();
    return ans1;
}
struct OfflineBit {
    vector <ll> tree, comp;
    void insert (ll x) {
        comp.push_back(x);
    }
    void build () {
        sort(comp.begin(), comp.end());
        comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
        tree.resize(comp.size());
        tree.insert(tree.begin(), 0);
    }
    int find (ll x) {
        return upper_bound(comp.begin(), comp.end(), x) - comp.begin();
    }
    inline int lsb (int x) {
        return x & (-x);
    }
    void add (ll x, ll y) {
        x = find(x);
        assert(x >= 0 && x < (int)(tree.size()));

        for (; x < int(tree.size()); x += lsb(x)) {
            tree[x] += y;
        }
    }
    ll get (ll x) {
        x = find(x);
        assert(x >= 0 && x < (int)(tree.size()));
        ll ret = 0;
        for (; x > 0; x -= lsb(x)) {
            ret += tree[x];
        }
        return ret;
    }
};
int solve2 () {
    ll u = k;
    for (auto j : path) {
        u -= f[j];
        f[j] = g[j] - f[j];
        g[j] = 1e18;
    }
    if (u < 0) {
        return -1;
    }
    vector <pair <ll, ll>> a;
    for (int i = 1; i <= n; i++) {
        a.push_back({g[i], f[i]});
    }
    sort(a.begin(), a.end());
    OfflineBit c1, c2;
    ll cur_sum = 0;
    c1.insert(0); c2.insert(0);
    for (auto i : a) {
        cur_sum += i.second;
        c1.insert(i.second); c1.insert(i.first - i.second);
        c2.insert(i.second); c2.insert(i.first - i.second);
        c1.insert(cur_sum); c2.insert(cur_sum);
    }
    c1.build(); c2.build();
    cur_sum = 0;
    for (auto i : a) {
        c1.add(i.second, 1); c2.add(i.second, i.second);
    }
    int ret = -1e9;
    auto val = [&] (int cnt) -> int {
        if (cur_sum > u) return -1e9;
        ll l = 0, r = 1e18, ans = -1;
        while (l <= r) {
            ll mid = (l + r) / 2;
            if (c2.get(mid) <= u - cur_sum) {
                l = mid + 1; ans = mid;
            } else {
                r = mid - 1;
            }
        }
        if (ans == -1) return -1e9;
        ll v = c1.get(ans + 1) - c1.get(ans);
        ll r2 = (u - cur_sum - c2.get(ans)) / (ans + 1);
        r2 = min(r2, v);
        return r2 + c1.get(ans) + cnt;
    };
    ret = val(0);
    int ee = 0;
    for (auto i : a) {
        ee++; cur_sum += i.second;
        c1.add(i.second, -1); c2.add(i.second, -i.second);
        c1.add(i.first - i.second, 1); c2.add(i.first - i.second, i.first - i.second);
        ret = max(ret, val(ee));
    }
    return ret + (int)path.size();
}
int max_score (int N2, int X2, int Y2, ll K2, vector <int> u, vector <int> v, vector <int> w) {
    n = N2; x = X2; y = Y2; k = K2;
    x++; y++;
    cur.clear(); path.clear();
    for (int i = 1; i <= n; i++) {
        adj[i].clear();
    }
    for (int i = 0; i + 1 < n; i++) {
        add_edge(u[i] + 1, v[i] + 1, w[i]);
    }
    dfs(x, -1, 0, 0);
    dfs(y, -1, 0, 1);
    dfs2(x, -1, y);
    for (int i = 1; i <= n; i++) {
        f[i] = min(dist[i][0], dist[i][1]);
        g[i] = max(dist[i][0], dist[i][1]);
    }
    int ret1 = solve1(), ret2 = solve2();
    return max(ret1, ret2);
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 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: 17 / 17