Submission #891250

#	Time	Username	Problem	Language	Result	Execution time	Memory
891250		Maaxle	Closing Time (IOI23_closing)	C++17	0 / 100	355 ms	38484 KiB

closing

#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 (stderr)

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
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17