Submission #1259072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259072		onbert	Closing Time (IOI23_closing)	C++20	8 / 100	786 ms	100804 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

struct thing {
    int val, j, id;
    bool operator < (const thing b) const {
        if (val != b.val) return val < b.val;
        if (j != b.j) return j < b.j;
        return id < b.id;
    }
};

const int maxn = 2e5 + 5, INF = 2e18 + 10;
int n, X, Y, k, D;
vector<pair<int,int>> adj[maxn];
int dist[maxn][2], state[maxn];
int cost1[maxn], cost2[maxn];

void dfs(int u, int j) {
    for (auto [v, w]:adj[u]) if (dist[v][j] == -1) {
        dist[v][j] = dist[u][j] + w;
        dfs(v, j);
    }
}

map<int, vector<pair<int,int>>> mp;
set<pair<int,int>> s1, s2;

vector<thing> ord;
int dc(thing x) {return lower_bound(ord.begin(), ord.end(), x) - ord.begin();}

int sz;
int fen[maxn * 3][2];
void update1(int id, int val, int j) {
    while (id <= sz) {
        fen[id][j] += val;
        id += (id & -id);
    }
}
int qry1(int id, int j) {
    int val = 0;
    while (id >= 1) {
        val += fen[id][j];
        id -= (id & -id);
    }
    return val;
}

multiset<int> hv1;

int ans, added, curans;

void update(int u, int x) {
    if (state[u] == 1) {
        int pos = dc({cost1[u], 1, u});
        update1(pos, -cost1[u], 0);
        update1(pos, -1, 1);
        hv1.erase(hv1.find(cost1[u]));
        s1.erase({cost1[u], u});
    } else if (state[u] == 2) {
        int pos = dc({cost2[u]/2, 2, u});
        update1(pos, -cost2[u]/2, 0);
        update1(pos, -1, 1);
        pos++;
        update1(pos, -cost2[u]/2, 0);
        update1(pos, -1, 1);
        s2.erase({cost2[u], u});
    } else if (state[u] == 3) {
        added -= cost1[u];
        curans--;
    } else if (state[u] == 4) {
        added -= cost2[u];
        curans -= 2;
    }
    state[u] = x;
    // cout << u << " " << cost1[u] << " " << cost2[u] << endl;
    if (x == 1) {
        int pos = dc({cost1[u], 1, u});
        update1(pos, cost1[u], 0);
        update1(pos, 1, 1);
        hv1.insert(cost1[u]);
        s1.insert({cost1[u], u});
    } else if (x == 2) {
        int pos = dc({cost2[u]/2, 2, u});
        update1(pos, cost2[u]/2, 0);
        update1(pos, 1, 1);
        pos++;
        update1(pos, cost2[u]/2, 0);
        update1(pos, 1, 1);
        s2.insert({cost2[u], u});
    } else if (x == 3) {
        added += cost1[u];
        curans++;
    } else if (x == 4) {
        added += cost2[u];
        curans += 2;
    }
}

int qry() {
    vector<int> S1 = {0};
    for (auto [x, i]:s1) S1.push_back(x);

    for (int i=1;i<S1.size();i++) S1[i] += S1[i-1];
    int cnt = 0, val = 0;
    int mx = upper_bound(S1.begin(), S1.end(), k - added) - S1.begin() - 1;
    for (auto [x, i]:s2) {
        cnt++, val += x;
        mx = max(cnt + (int)(upper_bound(S1.begin(), S1.end(), k - added - val) - S1.begin() - 1), mx);
    }
    return mx;

    // int l = 0, r = sz;
    // while (l < r) {
    //     int mid = (l + r + 1) / 2;
    //     if (qry1(mid, 0) + curans <= k) l = mid;
    //     else r = mid - 1;
    // }
    // int u = ord[l].id;
    // if (state[u] == 2 && l + 1 <= sz && ord[l+1].id == u) {
    //     if (qry1(l-1, 0) + *hv1.upper_bound(cost2[u]/2) > k && qry1(l+1, 0) - *prev(hv1.upper_bound(cost2[u]/2)) > k) {
    //         return qry1(l, 1) - 1;
    //     }
    // }
    // return qry1(l, 1);
}

int32_t max_score(int32_t N, int32_t XX, int32_t YY, int K, vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
    n = N, X = XX, Y = YY, k = K * 2;
    for (int i=0;i<n;i++) adj[i].clear();
    for (int i=0;i<U.size();i++) {
        adj[U[i]].push_back({V[i], W[i] * 2});
        adj[V[i]].push_back({U[i], W[i] * 2});
    }

    for (int i=0;i<n;i++) for (int j=0;j<=1;j++) dist[i][j] = -1;
    dist[X][0] = 0;
    dfs(X, 0);
    dist[Y][1] = 0;
    dfs(Y, 1);

    D = dist[Y][0];

    ord = {{0, -1, -1}};
    mp.clear();
    while (s1.size()) s1.erase(s1.begin());
    while (s2.size()) s2.erase(s2.begin());
    while (hv1.size()) hv1.erase(hv1.begin());
    hv1.insert(-INF); hv1.insert(INF);

    for (int i=0;i<n;i++) {
        cost1[i] = min(dist[i][0], dist[i][1]);
        cost2[i] = max(dist[i][0], dist[i][1]);
        int del = cost2[i] - cost1[i];
        mp[del].push_back({cost1[i], i});
        ord.push_back({cost1[i], 1, i});
        ord.push_back({cost2[i]/2, 2, i});
        ord.push_back({cost2[i]/2, 2, i});
        state[i] = 0;
    }

    sort(ord.begin(), ord.end());
    sz = (int)ord.size() - 1;
    for (int i=1;i<=sz;i++) fen[i][0] = fen[i][1] = 0;
    added = 0, curans = 0;
    for (int i=0;i<n;i++) state[i] = 0;
    for (int i=0;i<n;i++) update(i, 1);
    ans = qry();
    for (int i=0;i<n;i++) if (cost1[i] + cost2[i] == D) {
        update(i, 3);
    }

    for (auto [del, vec]:mp) {
        while (s1.size() && s1.begin()->first < del) {
            update(s1.begin()->second, 3);
        }
        while (s2.size() && s2.begin()->first < 2 * del) {
            update(s2.begin()->second, 4);
        }
        sort(vec.begin(), vec.end());
        for (auto [x, i]:vec) {
            if (cost1[i] + cost2[i] == D || cost1[i] < del) update(i, 3);
            else update(i, 2);
        }
        for (auto [x, i]:vec) {
            if (cost1[i] + cost2[i] == D || cost1[i] < del) {
                if (added + del <= k) update(i, 4);
            }
        }
        // cout << "start " << del/2 << " " << added/2 << endl;
        // for (int i=0;i<n;i++) cout << state[i] << " "; cout << endl;
        if (added <= k) {
            ans = max(qry() + curans, ans);
            // for (int i=1;i<=sz;i++) if (qry1(i, 1) - qry1(i-1, 1)) {
                // cout << ((double)qry1(i, 0) - qry1(i-1, 0))/2 << "." << ord[i].id << " ";
            // } cout << endl;
            // cout << "test " << del/2 << " " << ans << endl;
        }
        for (auto [x, i]:vec) {
            if (cost1[i] + cost2[i] == D) update(i, 4);
            else update(i, 2);
        }
    }
    return ans;
}

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