oj.uz

Submission #1065416

# Submission time Handle Problem Language Result Execution time Memory
1065416 2024-08-19T07:18:59 Z becaido Closing Time (IOI23_closing) C++17
37 / 100
 159 ms 36872 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]);
    }
    ans = 0;
    {
        priority_queue<ll, vector<ll>, greater<ll>> pq;
        FOR (i, 1, n) pq.push(a[i]);
        FOR (i, 1, n) pq.push(b[i]);
        ll cur = 0;
        while (pq.size() && cur + pq.top() <= k) {
            cur += pq.top();
            pq.pop();
            ans++;
        }
    }
    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];
        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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 36872 KB Output is correct
2 Correct 159 ms 36280 KB Output is correct
3 Correct 75 ms 19284 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 2 ms 16732 KB Output is correct
8 Correct 2 ms 16732 KB Output is correct
9 Correct 2 ms 16732 KB Output is correct
10 Correct 2 ms 16732 KB Output is correct
11 Correct 3 ms 16732 KB Output is correct

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 2 ms 16732 KB Output is correct
8 Correct 2 ms 16732 KB Output is correct
9 Correct 2 ms 16732 KB Output is correct
10 Correct 2 ms 16732 KB Output is correct
11 Correct 3 ms 16732 KB Output is correct
12 Correct 3 ms 16732 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 3 ms 16732 KB Output is correct
15 Correct 2 ms 16732 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 3 ms 16732 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 2 ms 16732 KB Output is correct
21 Incorrect 3 ms 16732 KB 1st lines differ - on the 1st token, expected: '884', found: '828'
22 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 2 ms 16732 KB Output is correct
8 Correct 2 ms 16732 KB Output is correct
9 Correct 2 ms 16732 KB Output is correct
10 Correct 2 ms 16732 KB Output is correct
11 Correct 3 ms 16732 KB Output is correct
12 Correct 3 ms 16732 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 3 ms 16732 KB Output is correct
15 Correct 2 ms 16732 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 3 ms 16732 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 2 ms 16732 KB Output is correct
21 Incorrect 3 ms 16732 KB 1st lines differ - on the 1st token, expected: '884', found: '828'
22 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 2 ms 16728 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 2 ms 16732 KB Output is correct
8 Correct 2 ms 16732 KB Output is correct
9 Correct 2 ms 16732 KB Output is correct
10 Correct 3 ms 16732 KB Output is correct
11 Correct 3 ms 16732 KB Output is correct
12 Correct 2 ms 16732 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 2 ms 16732 KB Output is correct
15 Correct 2 ms 16732 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 2 ms 16732 KB Output is correct
18 Correct 2 ms 16732 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 3 ms 16728 KB Output is correct
21 Correct 3 ms 16732 KB Output is correct
22 Correct 2 ms 16728 KB Output is correct
23 Correct 2 ms 16732 KB Output is correct
24 Correct 2 ms 16856 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 2 ms 16728 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 2 ms 16732 KB Output is correct
8 Correct 2 ms 16732 KB Output is correct
9 Correct 2 ms 16732 KB Output is correct
10 Correct 2 ms 16732 KB Output is correct
11 Correct 2 ms 16732 KB Output is correct
12 Correct 3 ms 16732 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 3 ms 16732 KB Output is correct
15 Correct 3 ms 16732 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 2 ms 16732 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 2 ms 16732 KB Output is correct
20 Correct 2 ms 16732 KB Output is correct
21 Correct 2 ms 16732 KB Output is correct
22 Correct 3 ms 16732 KB Output is correct
23 Correct 3 ms 16732 KB Output is correct
24 Correct 2 ms 16732 KB Output is correct
25 Correct 3 ms 16732 KB Output is correct
26 Correct 2 ms 16732 KB Output is correct
27 Correct 2 ms 16732 KB Output is correct
28 Correct 2 ms 16732 KB Output is correct
29 Correct 2 ms 16732 KB Output is correct
30 Correct 2 ms 16732 KB Output is correct
31 Correct 3 ms 16732 KB Output is correct
32 Correct 3 ms 16728 KB Output is correct
33 Correct 3 ms 16732 KB Output is correct
34 Correct 2 ms 16728 KB Output is correct
35 Correct 2 ms 16732 KB Output is correct
36 Correct 2 ms 16856 KB Output is correct
37 Correct 2 ms 16728 KB Output is correct
38 Correct 3 ms 16732 KB Output is correct
39 Correct 2 ms 16732 KB Output is correct
40 Correct 2 ms 16732 KB Output is correct
41 Correct 3 ms 16732 KB Output is correct
42 Correct 2 ms 16732 KB Output is correct
43 Correct 2 ms 16732 KB Output is correct
44 Correct 3 ms 16732 KB Output is correct
45 Correct 2 ms 16732 KB Output is correct
46 Correct 2 ms 16732 KB Output is correct
47 Correct 2 ms 16732 KB Output is correct
48 Correct 3 ms 16728 KB Output is correct
49 Correct 3 ms 16728 KB Output is correct
50 Correct 3 ms 16728 KB Output is correct

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 2 ms 16728 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 2 ms 16732 KB Output is correct
8 Correct 2 ms 16732 KB Output is correct
9 Correct 2 ms 16732 KB Output is correct
10 Correct 2 ms 16732 KB Output is correct
11 Correct 2 ms 16732 KB Output is correct
12 Correct 3 ms 16732 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 3 ms 16732 KB Output is correct
15 Correct 3 ms 16732 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 2 ms 16732 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 3 ms 16732 KB Output is correct
21 Correct 2 ms 16732 KB Output is correct
22 Incorrect 3 ms 16732 KB 1st lines differ - on the 1st token, expected: '884', found: '828'
23 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 2 ms 16728 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 2 ms 16732 KB Output is correct
8 Correct 2 ms 16732 KB Output is correct
9 Correct 2 ms 16732 KB Output is correct
10 Correct 2 ms 16732 KB Output is correct
11 Correct 2 ms 16732 KB Output is correct
12 Correct 3 ms 16732 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 3 ms 16732 KB Output is correct
15 Correct 3 ms 16732 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 2 ms 16732 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 3 ms 16732 KB Output is correct
21 Correct 2 ms 16732 KB Output is correct
22 Incorrect 3 ms 16732 KB 1st lines differ - on the 1st token, expected: '884', found: '828'
23 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 2 ms 16728 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 2 ms 16732 KB Output is correct
8 Correct 2 ms 16732 KB Output is correct
9 Correct 2 ms 16732 KB Output is correct
10 Correct 2 ms 16732 KB Output is correct
11 Correct 2 ms 16732 KB Output is correct
12 Correct 3 ms 16732 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 3 ms 16732 KB Output is correct
15 Correct 3 ms 16732 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 2 ms 16732 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 3 ms 16732 KB Output is correct
21 Correct 2 ms 16732 KB Output is correct
22 Incorrect 3 ms 16732 KB 1st lines differ - on the 1st token, expected: '884', found: '828'
23 Halted 0 ms 0 KB -