Submission #1065418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065418		becaido	Closing Time (IOI23_closing)	C++17	100 / 100	172 ms	40952 KiB

closing

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "closing.h"
#else
#include "grader.cpp"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const ll INF = 2e18;
const int SIZE = 2e5 + 5;

int n, x, y, ans;
int id[SIZE], p[SIZE][2];
vector<pair<int, int>> adj[SIZE];
tuple<ll, int, bool> v[SIZE << 1];
ll k, dx[SIZE], dy[SIZE], a[SIZE], b[SIZE];

void build(int s, ll *dis) {
    fill(dis + 1, dis + n + 1, INF);
    queue<int> q;
    dis[s] = 0;
    q.push(s);
    while (q.size()) {
        int pos = q.front();
        q.pop();
        for (auto [np, w] : adj[pos]) if (dis[pos] + w < dis[np]) {
            dis[np] = dis[pos] + w;
            q.push(np);
        }
    }
}

int bit[SIZE << 1];
ll sum[SIZE << 1];
void upd(int pos, int x, ll y) {
    for (; pos <= 2 * n; pos += pos & -pos) {
        bit[pos] += x;
        sum[pos] += y;
    }
}
int sch(ll k) {
    int pos = 0, re = 0;
    for (int i = __lg(2 * n); i >= 0; i--) {
        int nxt = pos + (1 << i);
        if (nxt <= 2 * n && sum[nxt] <= k) {
            k -= sum[nxt];
            re += bit[nxt];
            pos = nxt;
        }
    }
    return re;
}

int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
    n = N, x = X + 1, y = Y + 1, k = K;
    FOR (i, 1, n) adj[i].clear();
    FOR (i, 0, n - 2) {
        U[i]++, V[i]++;
        adj[U[i]].pb(V[i], W[i]);
        adj[V[i]].pb(U[i], W[i]);
    }
    build(x, dx), build(y, dy);
    FOR (i, 1, n) {
        a[i] = min(dx[i], dy[i]);
        b[i] = max(dx[i], dy[i]);
    }
    ans = 0;
    {
        priority_queue<ll, vector<ll>, greater<ll>> pq;
        FOR (i, 1, n) pq.push(a[i]);
        ll cur = 0;
        while (pq.size() && cur + pq.top() <= k) {
            cur += pq.top();
            pq.pop();
            ans++;
        }
    }
    int cnt = 0;
    ll cur = 0;
    fill(bit + 1, bit + 2 * n + 1, 0);
    fill(sum + 1, sum + 2 * n + 1, 0);
    FOR (i, 1, n) if (dx[i] + dy[i] == dx[y]) {
        cnt++;
        cur += a[i];
        a[i] = b[i] - a[i];
        b[i] = INF;
    }
    FOR (i, 1, n) {
        v[i] = {a[i], i, 0};
        v[n + i] = {b[i] - a[i], i, 1};
    }
    sort(v + 1, v + 2 * n + 1);
    FOR (i, 1, 2 * n) {
        auto [val, id, t] = v[i];
        p[id][t] = i;
    }
    FOR (i, 1, n) upd(p[i][0], 1, a[i]);
    if (cur <= k) ans = max(ans, cnt + sch(k - cur));
    iota(id + 1, id + n + 1, 1);
    sort(id + 1, id + n + 1, [&](int i, int j) {
        return b[i] < b[j];
    });
    FOR (i, 1, n) {
        upd(p[id[i]][0], -1, -a[id[i]]);
        if (dx[id[i]] + dy[id[i]] != dx[y]) upd(p[id[i]][1], 1, b[id[i]] - a[id[i]]);
        cnt++;
        cur += a[id[i]];
        if (cur <= k) ans = max(ans, cnt + sch(k - cur));
    }
    return ans;
}

/*
in1
2
7 0 2 10
0 1 2
0 3 3
1 2 4
2 4 2
2 5 5
5 6 3
4 0 3 20
0 1 18
1 2 1
2 3 19
out1
6
3
*/

• 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