oj.uz

Submission #891250

# Submission time Handle Problem Language Result Execution time Memory
891250 2023-12-22T15:16:36 Z Maaxle Closing Time (IOI23_closing) C++17
0 / 100
 355 ms 38484 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;

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

struct TPos {
    ll i;
};

bool operator < (const TPos& a, const TPos& b) {
    return (abs(from_y[a.i] - from_x[a.i]) < abs(from_y[b.i] - from_x[b.i]));
}


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

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

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);

    path_x.clear();
    path_x.resize(N);

    path_y.clear();
    path_y.resize(N);

    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, X);
    dfs_y(Y, 0, Y);

    pqueue<TPos> pq;
    vector<ll> memo_x (N), memo_y(N);
    ll sum = 0;
    range(i, 0, N) {
        if (adj[i].size() == 1)
            pq.push({i});
        sum += max(from_x[i], from_y[i]);
    }

    while (sum > K) {
        TPos t = pq.top(); pq.pop();
        if (!from_x[t.i] && !from_y[t.i]) continue;

        if (from_y[t.i] == from_x[t.i] && memo_x[t.i] == adj[t.i].size() - 1 && memo_y[t.i] == adj[t.i].size() - 1) {
            // cout << "BOTH:" << t.i << ":" << from_y[t.i] << '\n';
            sum -= from_y[t.i];
            ans -= 2;
            from_y[t.i] = from_x[t.i] = 0;
            memo_x[path_x[t.i]]++;
            memo_y[path_y[t.i]]++;
            pq.push({path_x[t.i]});
            pq.push({path_y[t.i]});
        }
        else if (from_x[t.i] > from_y[t.i] && memo_x[t.i] == adj[t.i].size() - 1) {
            ll dif = from_x[t.i] - from_y[t.i];
            // cout << "X:" << t.i << ':' << dif << '\n';
            ans--;
            sum -= dif;
            from_x[t.i] = 0;
            memo_x[path_x[t.i]]++;
            pq.push({path_x[t.i]});
            pq.push(t);
        }
        else if (from_y[t.i] > from_x[t.i] && memo_y[t.i] == adj[t.i].size() - 1) {
            ll dif = from_y[t.i] - from_x[t.i];
            // cout << "Y:" << t.i << ':' << dif << '\n';
            ans--;
            sum -= dif;
            from_y[t.i] = 0;
            memo_y[path_y[t.i]]++;
            pq.push({path_y[t.i]});
            pq.push(t);
        }
    }

    // cout << "-------------------\n";
    return ans;
}

Compilation message

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:87:55: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         if (from_y[t.i] == from_x[t.i] && memo_x[t.i] == adj[t.i].size() - 1 && memo_y[t.i] == adj[t.i].size() - 1) {
closing.cpp:87:93: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         if (from_y[t.i] == from_x[t.i] && memo_x[t.i] == adj[t.i].size() - 1 && memo_y[t.i] == adj[t.i].size() - 1) {
closing.cpp:97:59: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         else if (from_x[t.i] > from_y[t.i] && memo_x[t.i] == adj[t.i].size() - 1) {
closing.cpp:107:59: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         else if (from_y[t.i] > from_x[t.i] && memo_y[t.i] == adj[t.i].size() - 1) {

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 355 ms 38484 KB 1st lines differ - on the 1st token, expected: '451', found: '260'
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '26', found: '24'
4 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 1 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '26', found: '24'
4 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 1 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '26', found: '24'
4 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 1 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '26', found: '24'
5 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 1 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '26', found: '24'
5 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 1 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '26', found: '24'
5 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 1 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '26', found: '24'
5 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 1 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '26', found: '24'
5 Halted 0 ms 0 KB -