Submission #962993

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
962993	2024-04-14T10:33:43 Z	tutis	Closing Time (IOI23_closing)	C++17	Compilation error	0 ms	0 KB

closing

#include "closing.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int max_score(int N, int X, int Y, long long K,
              vector<int> U, vector<int> V, vector<int> W) {
    vector <pair<int, int>> adj[N];
    vector <vector<int>> adj1[2];
    adj1[0] = vector < vector < int >> (N);
    adj1[1] = vector < vector < int >> (N);
    for (int i = 0; i < N - 1; i++) {
        adj[U[i]].push_back({V[i], W[i]});
        adj[V[i]].push_back({U[i], W[i]});
    }
    vector <ll> D[2];
    D[0] = vector<ll>(N);
    D[1] = vector<ll>(N);
    int XY[2] = {X, Y};
    vector<int> x2y;
    for (int t: {0, 1}) {
        D[t][XY[t]] = 0;
        vector<int> P;
        function<void(int, int)> dfs = [&](int i, int p) -> void {
            if (p != -1) {
                adj1[t][p].push_back(i);
            }
            P.push_back(i);
            if (t == 0 && i == Y) {
                x2y = P;
            }
            for (auto j: adj[i]) {
                if (j.first == p) {
                    continue;
                }
                D[t][j.first] = D[t][i] + j.second;
                dfs(j.first, i);
            }
            P.pop_back();
        };
        dfs(XY[t], -1);
    }
    int ret = 0;
    vector <ll> cost[2];
    for (int t: {0, 1}) {
        ll sum = 0;
        priority_queue <pair<int, int>> Q;
        Q.push({0, XY[t]});
        while (!Q.empty()) {
            int i = Q.top().second;
            Q.pop();
            sum += D[t][i];
            cost[t].push_back(sum);
            if (sum > K) {
                break;
            }
            for (auto j: adj1[t][i]) {
                Q.push({-D[t][j], j});
            }
        }
    }
    for (int i = 0; i < cost[0].size(); i++) {
        for (int j = 0; j < cost[1].size(); j++) {
            if (cost[0][i] + cost[1][j] <= K) {
                ret = max(ret, i + 1 + j + 1);
            }
        }
    }

    int m = 0;
    while (m + 1 < x2y.size() && D[0][x2y[m + 1]] <= D[1][x2y[m + 1]]) {
        m++;
    }
    ll s0 = 0;
    ll s1 = 0;
    for (int i = 0; i <= m; i++) {
        s0 += D[0][x2y[i]];
        s0 = min(s0, K + 1);
    }
    for (int j = x2y.size() - 1; j > m; j--) {
        s1 += D[1][x2y[j]];
        s1 = min(s1, K + 1);
    }
    if (s0 + s1 > K) {
        return ret;
    }
    K -= s0 + s1;
    bool free[N];
    for (int i = 0; i < N; i++) {
        free[i] = false;
    }
    for (int i: x2y) {
        free[i] = true;
    }

    auto merge = [&](const vector <ll> &a, const vector <ll> &b) {
        vector <ll> r(a.size() + b.size() - 1, K + 1);
        int ai = 0;
        for (int i = 0; i < r.size(); i++) {
            int amin = max(0, i - int(b.size()) + 1);
            int amax = min(a.size() - 1, i);
            ai = max(amin, ai);
            ai = min(amin, ai);
            auto fn = [&](int ai) -> ll {
                if (ai < amin || ai > amax) {
                    return 3e18;
                }
                return a[ai] + b[i - ai];
            };
            while (fn(ai - 1) > fn(ai)) {
                ai--;
            }
            while (fn(ai + 1) > fn(ai)) {
                ai++;
            }
            r[i] = fn(ai);
        }
        return r;
    };

    function < array < vector < ll > , 2 > (int, int, int) > fn = [&](int t, int i, int p) -> array<vector<ll>, 2> {
        vector <ll> ch[2] = {{0},
                             {0}};
        for (auto j: adj[i]) {
            if (j.first == p) {
                continue;
            }
            auto arrs = fn(t, j.first, i);
            ch[0] = merge(ch[0], arrs[0]);
            ch[1] = merge(ch[1], arrs[1]);
        }
        ll buyX = D[t][i];
        ll buyY = D[1 - t][i];
        int fr = 0;
        if (free[i]) {
            fr = 1;
            buyX = 0;
            buyY -= D[t][i];
        }
        vector <ll> m1 = {0};
        if (!fr) {
            m1 = {0, buyX};
        }
        ch[0] = merge(ch[0], m1);
        array<vector<ll>, 2> ret;
        ret[0] = ch[0];
        ret[1] = ch[0];
        for (int i = 0; i < ch[1].size(); i++) {
            int ii = i + 2 - fr;
            while (ii >= ret[1].size()) {
                ret[1].push_back(K + 1);
            }
            ret[1][ii] = min(ret[1][ii], ch[1][i] + buyY);
        }
        return ret;
    };

    auto cost0 = fn(0, x2y[m], x2y[m + 1])[1];
    auto cost1 = fn(1, x2y[m + 1], x2y[m])[1];
    auto ans = merge(cost0, cost1);
    for (int i = 0; i < ans.size(); i++) {
        if (ans[i] <= K) {
            ret = max(ret, i + int(x2y.size()));
        }
    }

    return ret;
}

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:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < cost[0].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
closing.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int j = 0; j < cost[1].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~
closing.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     while (m + 1 < x2y.size() && D[0][x2y[m + 1]] <= D[1][x2y[m + 1]]) {
      |            ~~~~~~^~~~~~~~~~~~
closing.cpp: In lambda function:
closing.cpp:102:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for (int i = 0; i < r.size(); i++) {
      |                         ~~^~~~~~~~~~
closing.cpp:104:43: error: no matching function for call to 'min(std::vector<long long int>::size_type, int&)'
  104 |             int amax = min(a.size() - 1, i);
      |                                           ^
In file included from /usr/include/c++/10/vector:60,
                 from closing.h:1,
                 from closing.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
closing.cpp:104:43: note:   deduced conflicting types for parameter 'const _Tp' ('long unsigned int' and 'int')
  104 |             int amax = min(a.size() - 1, i);
      |                                           ^
In file included from /usr/include/c++/10/vector:60,
                 from closing.h:1,
                 from closing.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
closing.cpp:104:43: note:   deduced conflicting types for parameter 'const _Tp' ('long unsigned int' and 'int')
  104 |             int amax = min(a.size() - 1, i);
      |                                           ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from closing.cpp:3:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
closing.cpp:104:43: note:   mismatched types 'std::initializer_list<_Tp>' and 'long unsigned int'
  104 |             int amax = min(a.size() - 1, i);
      |                                           ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from closing.cpp:3:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
closing.cpp:104:43: note:   mismatched types 'std::initializer_list<_Tp>' and 'long unsigned int'
  104 |             int amax = min(a.size() - 1, i);
      |                                           ^
closing.cpp: In lambda function:
closing.cpp:151:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |         for (int i = 0; i < ch[1].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~
closing.cpp:153:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |             while (ii >= ret[1].size()) {
      |                    ~~~^~~~~~~~~~~~~~~~
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:164:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |     for (int i = 0; i < ans.size(); i++) {
      |                     ~~^~~~~~~~~~~~