답안 #888933

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888933	2023-12-18T12:13:13 Z	ZHIRDILBILDIZ	봉쇄 시간 (IOI23_closing)	C++17	컴파일 오류	0 ms	0 KB

closing

#include<bits/stdc++.h>
#include "closing.h"
#define fi first
#define se second
#define ll long long
using namespace std;
const ll N = 2e5 + 10;
bitset<N> us;
vector<pair<ll, ll>> gr[N];
ll dist[N][2];
ll ds[N][2];
bool flag;
void ultra_clear(int n) {
    flag &= 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 2; ++j)
            dist[i][j] &= 0,
                ds[i][j] &= 0;
        gr[i].clear();
        us[i] = 0;
    }
}
void pre_calc(ll city, ll last, ll type) {
    for (auto i : gr[city]) {
        if (i.fi == last)
            continue;
        dist[i.fi][type] = dist[city][type] + i.se;
        pre_calc(i.fi, city, type);
    }
}
void get_path(int city, int last, int y, vector<int> &path) {
    if (!flag)
        path.push_back(city);
    if (city == y) {
        flag = 1;
        return;
    }
    for (auto i : gr[city]) {
        if (i.fi == last)
            continue;
        get_path(i.fi, city, y, path);
    }
    if (!flag)
        path.pop_back();
}
int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w) {
    ultra_clear(n);
    int m = n - 1, ans = 0;
    for (ll i = 0; i < m; ++i) {
        gr[u[i]].push_back({v[i], w[i]});
        gr[v[i]].push_back({u[i], w[i]});
    }
    dist[x][0] = dist[y][1] &= 0;
    pre_calc(x, 0, 0);
    pre_calc(y, 0, 1);
    set<pair<ll, ll>> stx, sty;
    vector<ll> path;
    get_path(x, 0, y, path);
    ll psz = path.size() - 1;
    for (ll i = 0; i < path.size(); ++i) {
        for (ll j = 0; j < path.size(); ++j) {

            ll hp = k;
            ll cnt = 0;
            ll now[n] = {};

            for (ll q = 0; q < n; ++q)
                ds[q][0] = dist[q][0],
                    ds[q][1] = dist[q][1];

            for (ll q = 0; q < i - 1; ++q)
                now[path[q]] = max(now[path[q]], dist[path[q]][0]);

            for (ll q = 0; q < j - 1; ++q)
                now[path[psz - q]] = max(now[path[psz - q]], dist[path[psz - q]][1]);

            for (ll q = 0; q <= psz; ++q) {
                for (ll z = 0; z < 2; ++z)
                    ds[path[q]][z] = max(0ll, ds[path[q]][z] - now[path[q]]);
                hp -= now[path[q]];
            }

            if (hp < 0)
                break;

            set<pair<ll, ll>> stx, sty;

            for (ll i = 0; i < n; ++i)
                stx.insert({ds[i][0], i}),
                    sty.insert({ds[i][1], i});

            while (stx.size() || sty.size()) {
                pair<ll, ll> p1 = {1e18, 1e18}, p2 = {1e18, 1e18};
                if (stx.size())
                    p1 = *stx.begin();
                if (sty.size())
                    p2 = *sty.begin();
                if (p1.fi <= p2.fi) {
                    if (hp - p1.fi < 0)
                        break;
                    hp -= p1.fi;
                    sty.erase({max(0ll, dist[p1.se][1] - now[p1.se]), p1.se});
                    now[p1.se] += p1.fi;
                    stx.insert({max(0ll, dist[p1.se][0] - now[p2.se]), p2.se});
                    stx.erase(stx.begin());
                } else {
                    if (hp - p2.fi < 0)
                        break;
                    hp -= p2.fi;
                    stx.erase({max(0ll, dist[p1.se][0] - now[p2.se]), p2.se});
                    now[p2.se] += p2.fi;
                    stx.insert({max(0ll, dist[p1.se][0] - now[p2.se]), p2.se});
                    sty.erase(sty.begin());
                }
                ++cnt;
            }

            ans = max(ans, cnt);
        }
    }
    return ans;
}
//signed main() {
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    int t;
//    cin >> t;
//    while (t--) {
//        int n;
//        int x, y;
//        ll k;
//        cin >> n >> x >> y >> k;
//        vector<int> u(n - 1), v(n - 1), w(n - 1);
//        for (int i = 0; i < n - 1; ++i)
//            cin >> u[i] >> v[i] >> w[i];
//        cout << max_score(n, x, y, k, u, v, w);
//    }
//    return 0;
//}
//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

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:58:23: error: invalid initialization of reference of type 'std::vector<int>&' from expression of type 'std::vector<long long int>'
   58 |     get_path(x, 0, y, path);
      |                       ^~~~
closing.cpp:31:55: note: in passing argument 4 of 'void get_path(int, int, int, std::vector<int>&)'
   31 | void get_path(int city, int last, int y, vector<int> &path) {
      |                                          ~~~~~~~~~~~~~^~~~
closing.cpp:60:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (ll i = 0; i < path.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~
closing.cpp:61:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (ll j = 0; j < path.size(); ++j) {
      |                        ~~^~~~~~~~~~~~~
closing.cpp:118:31: error: no matching function for call to 'max(int&, long long int&)'
  118 |             ans = max(ans, cnt);
      |                               ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from closing.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
closing.cpp:118:31: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  118 |             ans = max(ans, cnt);
      |                               ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from closing.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
closing.cpp:118:31: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  118 |             ans = max(ans, cnt);
      |                               ^
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:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
closing.cpp:118:31: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  118 |             ans = max(ans, cnt);
      |                               ^
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:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
closing.cpp:118:31: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  118 |             ans = max(ans, cnt);
      |                               ^