제출 #1125855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125855		tgh317127	Museum (CEOI17_museum)	C++20	컴파일 에러	0 ms	0 KiB

museum

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define MASK(i) ((1LL) << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define fi first
#define se second

using namespace std;

const long inf = 1e9 + 7;
const long mod = 1e9 + 7;
const long Nmax = 1e4 + 7;
const long lg = 20;
const long bs = 1003;

int n, k, x;
vector<pii> g[Nmax];
pll dp[Nmax][Nmax];
pll pref[Nmax];
int sz[Nmax];

void combine(int u, int v, int c)
{
    for (int i = 1; i <= sz[u]; i++)
    {
        for (int j = 1; j <= sz[v]; j++)
        {
            if (i + j > sz[u]) break;
            pll val = pref[i];
            val.fi += dp[v][j].fi + 2 * c;
            val.se = max(val.se, dp[v][j].se + c);
//            cerr << val.fi << " " << val.se << "\n";
            if (dp[u][i + j].fi - dp[u][i + j].se > val.fi - val.se) dp[u][i + j] = val;
            else if (dp[u][i + j] - dp[u][i + j].se == val.fi - val.se)
            {
                if (dp[u][i + j].fi > val.fi) dp[u][i + j] = val;
            }
        }
    }
    for (int i = 1; i <= sz[u]; i++)
    {
        if (pref[i].fi - pref[i].se > dp[u][i].fi - dp[u][i].se) pref[i] = dp[u][i];
//        cerr << dp[u][i].fi << " " << dp[u][i].se << "\n";
    }
}

void dfs(int u, int p)
{
    sz[u] = 1;
    for (auto v : g[u])
    {
        if (v.fi == p) continue;
        dfs(v.fi, u);
        sz[u] += sz[v.fi];
    }
    for (int i = 0; i <= sz[u]; i++) pref[i] = {1LL * inf * inf, -1LL * inf * inf};
    pref[1] = {0, 0};
    for (auto v : g[u])
    {
        if (v.fi == p) continue;
        combine(u, v.fi, v.se);
    }
    dp[u][0] = {0, 0};
    dp[u][1] = {0, 0};
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("name.inp","r",stdin);
    //freopen("name.out","w",stdout);
    cin >> n >> k >> x;
    for (int i = 1; i < n; i++)
    {
        int u, v, c;
        cin >> u >> v >> c;
        g[u].push_back({v, c});
        g[v].push_back({u, c});
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = {1LL * inf * inf, -1LL * inf * inf};

    dfs(x, -1);
//    for (int i = 0; i <= 10; i++) cerr << dp[7][i].fi << " " << dp[7][i].se << "\n";
//    ll res = 8 * 1LL * inf * inf;
//    for (int i = 1; i <= n; i++)
//    {
//        res = min(res, dp[i][k].fi - dp[i][k].se);
////        cerr << dp[i][k].fi << " " << dp[i][k].se << "\n";
//    }
//    cout << res << "\n";
    cout << dp[x][k].fi - dp[x][k].se << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

museum.cpp: In function 'void combine(int, int, int)':
museum.cpp:37:35: error: no match for 'operator-' (operand types are 'std::pair<long long int, long long int>' and 'long long int')
   37 |             else if (dp[u][i + j] - dp[u][i + j].se == val.fi - val.se)
      |                      ~~~~~~~~~~~~ ^
      |                                 |
      |                                 std::pair<long long int, long long int>
In file included from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from museum.cpp:1:
/usr/include/c++/11/bits/stl_iterator.h:577:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_IteratorL>&, const std::reverse_iterator<_IteratorR>&)'
  577 |     operator-(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/11/bits/stl_iterator.h:577:5: note:   template argument deduction/substitution failed:
museum.cpp:9:12: note:   'std::pair<long long int, long long int>' is not derived from 'const std::reverse_iterator<_IteratorL>'
    9 | #define se second
      |            ^~~~~~
museum.cpp:37:50: note: in expansion of macro 'se'
   37 |             else if (dp[u][i + j] - dp[u][i + j].se == val.fi - val.se)
      |                                                  ^~
In file included from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from museum.cpp:1:
/usr/include/c++/11/bits/stl_iterator.h:1693:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
 1693 |     operator-(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/11/bits/stl_iterator.h:1693:5: note:   template argument deduction/substitution failed:
museum.cpp:9:12: note:   'std::pair<long long int, long long int>' is not derived from 'const std::move_iterator<_IteratorL>'
    9 | #define se second
      |            ^~~~~~
museum.cpp:37:50: note: in expansion of macro 'se'
   37 |             else if (dp[u][i + j] - dp[u][i + j].se == val.fi - val.se)
      |                                                  ^~
In file included from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from museum.cpp:1:
/usr/include/c++/11/complex:362:5: note: candidate: 'template<class _Tp> constexpr std::complex<_Tp> std::operator-(const std::complex<_Tp>&, const std::complex<_Tp>&)'
  362 |     operator-(const complex<_Tp>& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/11/complex:362:5: note:   template argument deduction/substitution failed:
museum.cpp:9:12: note:   'std::pair<long long int, long long int>' is not derived from 'const std::complex<_Tp>'
    9 | #define se second
      |            ^~~~~~
museum.cpp:37:50: note: in expansion of macro 'se'
   37 |             else if (dp[u][i + j] - dp[u][i + j].se == val.fi - val.se)
      |                                                  ^~
In file included from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from museum.cpp:1:
/usr/include/c++/11/complex:371:5: note: candidate: 'template<class _Tp> constexpr std::complex<_Tp> std::operator-(const std::complex<_Tp>&, const _Tp&)'
  371 |     operator-(const complex<_Tp>& __x, const _Tp& __y)
      |     ^~~~~~~~
/usr/include/c++/11/complex:371:5: note:   template argument deduction/substitution failed:
museum.cpp:9:12: note:   'std::pair<long long int, long long int>' is not derived from 'const std::complex<_Tp>'
    9 | #define se second
      |            ^~~~~~
museum.cpp:37:50: note: in expansion of macro 'se'
   37 |             else if (dp[u][i + j] - dp[u][i + j].se == val.fi - val.se)
      |                                                  ^~
In file included from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from museum.cpp:1:
/usr/include/c++/11/complex:380:5: note: candidate: 'template<class _Tp> constexpr std::complex<_Tp> std::operator-(const _Tp&, const std::complex<_Tp>&)'
  380 |     operator-(const _Tp& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/11/complex:380:5: note:   template argument deduction/substitution failed:
museum.cpp:9:12: note:   mismatched types 'const std::complex<_Tp>' and 'long long int'
    9 | #define se second
      |            ^~~~~~
museum.cpp:37:50: note: in expansion of macro 'se'
   37 |             else if (dp[u][i + j] - dp[u][i + j].se == val.fi - val.se)
      |                                                  ^~
In file included from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from museum.cpp:1:
/usr/include/c++/11/complex:457:5: note: candidate: 'template<class _Tp> constexpr std::complex<_Tp> std::operator-(const std::complex<_Tp>&)'
  457 |     operator-(const complex<_Tp>& __x)
      |     ^~~~~~~~
/usr/include/c++/11/complex:457:5: note:   template argument deduction/substitution failed:
museum.cpp:9:12: note:   'std::pair<long long int, long long int>' is not derived from 'const std::complex<_Tp>'
    9 | #define se second
      |            ^~~~~~
museum.cpp:37:50: note: in expansion of macro 'se'
   37 |             else if (dp[u][i + j] - dp[u][i + j].se == val.fi - val.se)
      |                                                  ^~
In file included from /usr/include/c++/11/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:95,
                 from museum.cpp:1:
/usr/include/c++/11/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom1, class _Dom2> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::_Expr<_Dom2, typename _Dom2::value_type>&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, struct std::__minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
museum.cpp:9:12: note:   'std::pair<long long int, long long int>' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
    9 | #define se second
      |            ^~~~~~
museum.cpp:37:50: note: in expansion of macro 'se'
   37 |             else if (dp[u][i + j] - dp[u][i + j].se == val.fi - val.se)
      |                                                  ^~
In file included from /usr/include/c++/11/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:95,
                 from museum.cpp:1:
/usr/include/c++/11/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Expr, std::_Constant, _Dom, typename _Dom::value_type>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const typename _Dom::value_type&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, struct std::__minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
museum.cpp:9:12: note:   'std::pair<long long int, long long int>' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
    9 | #define se second
      |            ^~~~~~
museum.cpp:37:50: note: in expansion of macro 'se'
   37 |             else if (dp[u][i + j] - dp[u][i + j].se == val.fi - val.se)
      |                                                  ^~
In file included from /usr/include/c++/11/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:95,
                 from museum.cpp:1:
/usr/include/c++/11/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Constant, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const typename _Dom::value_type&, const std::_Expr<_Dom1, typename _Dom1::value_type>&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, struct std::__minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
museum.cpp:9:12: note:   mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'long long int'
    9 | #define se second
      |            ^~~~~~
museum.cpp:37:50: note: in expansion of macro 'se'
   37 |             else if (dp[u][i + j] - dp[u][i + j].se == val.fi - val.se)
      |                                                  ^~
In file included from /usr/include/c++/11/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:95,
                 from museum.cpp:1:
/usr/include/c++/11/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Expr, std::_ValArray, _Dom, typename _Dom::value_type>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::valarray<typename _Dom::value_type>&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, struct std::__minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
museum.cpp:9:12: note:   'std::pair<long long int, long long int>' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
    9 | #define se second
      |            ^~~~~~
museum.cpp:37:50: note: in expansion of macro 'se'
   37 |             else if (dp[u][i + j] - dp[u][i + j].se == val.fi - val.se)
      |                                                  ^~
In file included from /usr/include/c++/11/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:95,
                 from museum.cpp:1:
/usr/include/c++/11/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_ValArray, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const std::valarray<typename _Dom::value_type>&, const std::_Expr<_Dom1, typename _Dom1::value_type>&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, struct std::__minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
museum.cpp:9:12: note:   mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'long long int'
    9 | #define se second
      |            ^~~~~~
museum.cpp:37:50: note: in expansion of macro 'se'
   37 |             else if (dp[u][i + j] - dp[u][i + j].se == val.fi - val.se)
      |                                                  ^~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:95,
                 from museum.cpp:1:
/usr/include/c++/11/valarray:1187:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__minus, std::_ValArray, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__minus, _Tp>::result_type> std::operator-(const std::valarray<_Tp>&, const std::valarray<_Tp>&)'
 1187 | _DEFINE_BINARY_OPERATOR(-, __minus)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/valarray:1187:1: note:   template argument deduction/substitution failed:
museum.cpp:9:12: note:   'std::pair<long long int, long long int>' is not derived from 'const std::valarray<_Tp>'
    9 | #define se second
      |            ^~~~~~
museum.cpp:37:50: note: in expansion of macro 'se'
   37 |             else if (dp[u][i + j] - dp[u][i + j].se == val.fi - val.se)
      |                                                  ^~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:95,
                 from museum.cpp:1:
/usr/include/c++/11/valarray:1187:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__minus, std::_ValArray, std::_Constant, _Tp, _Tp>, typename std::__fun<std::__minus, _Tp>::result_type> std::operator-(const std::valarray<_Tp>&, const typename std::valarray<_Tp>::value_type&)'
 1187 | _DEFINE_BINARY_OPERATOR(-, __minus)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/valarray:1187:1: note:   template argument deduction/substitution failed:
museum.cpp:9:12: note:   'std::pair<long long int, long long int>' is not derived from 'const std::valarray<_Tp>'
    9 | #define se second
      |            ^~~~~~
museum.cpp:37:50: note: in expansion of macro 'se'
   37 |             else if (dp[u][i + j] - dp[u][i + j].se == val.fi - val.se)
      |                                                  ^~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:95,
                 from museum.cpp:1:
/usr/include/c++/11/valarray:1187:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Constant, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__minus, _Tp>::result_type> std::operator-(const typename std::valarray<_Tp>::value_type&, const std::valarray<_Tp>&)'
 1187 | _DEFINE_BINARY_OPERATOR(-, __minus)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/valarray:1187:1: note:   template argument deduction/substitution failed:
museum.cpp:9:12: note:   mismatched types 'const std::valarray<_Tp>' and 'long long int'
    9 | #define se second
      |            ^~~~~~
museum.cpp:37:50: note: in expansion of macro 'se'
   37 |             else if (dp[u][i + j] - dp[u][i + j].se == val.fi - val.se)
      |                                                  ^~