oj.uz

Submission #890764

# Submission time Handle Problem Language Result Execution time Memory
890764 2023-12-22T02:32:26 Z Maaxle Closing Time (IOI23_closing) C++17
8 / 100
 180 ms 39620 KB 
#include "closing.h"
#include <bits/stdc++.h>

#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 60)
#define INF32 ((ll) 1 << 30)
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue

using namespace std;

struct TPos {
    ll X, Y;
};

bool operator < (const TPos& a, const TPos& b) {
    return (max(a.X, a.Y) < max(b.X, b.Y));
}

vector<vector<pair<ll, ll>>> adj;
vector<ll> from_x, from_y;

void dfs_x (ll i, ll cnt) {
    from_x[i] = cnt;
    for (pair<ll, ll> k : adj[i]) {
        if (from_x[k.first] == INF64) {
            dfs_x(k.first, cnt + k.second);
        }
    }
}

void dfs_y (ll i, ll cnt) {
    from_y[i] = cnt;
    for (pair<ll, ll> k : adj[i]) {
        if (from_y[k.first] == INF64) {
            dfs_y(k.first, cnt + k.second);
        }
    }
}

int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
    adj.clear();
    adj.resize(N);

    from_x.clear();
    from_x.resize(N, INF64);

    from_y.clear();
    from_y.resize(N, INF64);

    range(i, 0, N - 1){
        adj[U[i]].push_back({V[i], W[i]});
        adj[V[i]].push_back({U[i], W[i]});
    }

    ll ans = 2*N;
    dfs_x(X, 0);
    dfs_y(Y, 0);

    pqueue<TPos> pq;
    ll sum = 0;
    range(i, 0, N) {
        pq.push({from_x[i], from_y[i]});
        sum += max(from_x[i], from_y[i]);
    }

    while (sum > K) {
        TPos t = pq.top(); pq.pop();
        
        if (t.X > t.Y) {
            ll dif = t.X - t.Y;
            t.X = 0;
            ans--;
            sum -= dif;
        }
        else {
            ll dif = t.Y - t.X;
            t.Y = 0;
            ans--;
            sum -= dif;
        }

        pq.push(t);
    }

    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 32452 KB Output is correct
2 Correct 180 ms 39620 KB Output is correct
3 Correct 90 ms 5468 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
8 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
8 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
8 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
8 Halted 0 ms 0 KB -