oj.uz

Submission #1065312

# Submission time Handle Problem Language Result Execution time Memory
1065312 2024-08-19T06:13:35 Z becaido Closing Time (IOI23_closing) C++17
8 / 100
 141 ms 36764 KB 
#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(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]);
        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;
    }
    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++;
        }
    }
    iota(id + 1, id + n + 1, 1);
    sort(id + 1, id + n + 1, [&](int i, int j) {
        return b[i] < b[j];
    });
    ll cur = 0;
    int cnt = 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];
            upd(p[i][1], 1, b[i] - a[i]);
        } else {
            upd(p[i][0], 1, a[i]);
        }
    }
    FOR (i, 1, n) {
        if (dx[id[i]] + dy[id[i]] != dx[y]) {
            upd(p[id[i]][0], -1, -a[id[i]]);
            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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 36764 KB Output is correct
2 Correct 139 ms 36260 KB Output is correct
3 Correct 75 ms 7760 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5208 KB Output is correct
4 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '34', found: '31'
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5208 KB Output is correct
4 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '34', found: '31'
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5208 KB Output is correct
4 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '34', found: '31'
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '34', found: '31'
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '34', found: '31'
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '34', found: '31'
6 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '34', found: '31'
6 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '34', found: '31'
6 Halted 0 ms 0 KB -