Submission #1262592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262592		dungmahiru	Museum (CEOI17_museum)	C++17	Compilation error	0 ms	0 KiB

museum

#include <bits/stdc++.h>
using namespace std;
#define ShiinaMahiru signed main()
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

typedef long long ll;
#define int ll              // Neu can thiet
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;

#define el "\n"
#define gcd __gcd
#define lcm(a, b) a / gcd(a,b) * b
#define get_bit(mask, i) ((mask >> i) & 1)
#define set_bit(mask, i) (mask | (1<<(i)))
#define low_bit(mask) (mask & (-mask))
#define pb push_back
#define emp emplace
#define emb emplace_back
#define emf emplace_front
#define mpair make_pair
#define fi first
#define se second
#define rounds(n) setprecision(n) << fixed

const int INF = 0x3f3f3f3f;
const ll LLINF = (ll)1e18+3;
const int MAXSIZE = (int)1e5+7;
const int MOD = (int)1e9+7;
const string NAME = "test";

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
ll Rand(ll L, ll R) { assert(L <= R); return L + rd() % (R - L + 1); }

template <class T> inline bool minimize(T &x, T y){ if (x > y){x = y; return true;} return false; }
template <class T> inline bool maximize(T &x, T y){ if (x < y){x = y; return true;} return false; }

int N, K, X;
vector<pii> adj[MAXSIZE];

void INPUT()
{
    cin >> N >> K >> X;
    for (int i = 2; i <= N; ++i){
        int u, v, c; 
        cin >> u >> v >> c;
        adj[u].pb({v, c});
        adj[v].pb({u, c});
    }
}

int dp[MAXSIZE][MAXSIZE][2];
int cnt[MAXSIZE];

void dfs(int u, int p)
{
    cnt[u] = 1;
    dp[u][1][0] = dp[u][1][1] = 0;

    for (pii e : adj[u]){
        int v = e.fi, c = e.se;
        if (v == p) continue;
        dfs(v, u);
        for (int j = min(K, cnt[u]); j >= 1; --j){
            for (int k = min(K - j, cnt[v]); k >= 1; --k){
                minimize(dp[u][j + k][0], dp[u][j][0] + dp[v][k][0] + 2*c);

                minimize(dp[u][j + k][1], dp[u][j][1] + dp[v][k][0] + 2*c);
                minimize(dp[u][j + k][1], dp[u][j][0] + dp[v][k][1] + c);
            }
        }

        cnt[u] += cnt[v];
    }
}

void SOLVE()
{
    for (int i = 1; i <= N; ++i){
        for (int j = 1; j <= N; ++j){
            dp[i][j][0] = dp[i][j][1] = LLINF;
        }
    }

    dfs(X, -1);
    cout << min(dp[X][K][0], dp[X][K][1]);
}

ShiinaMahiru
{
    FAST_IO;
    clock_t start = clock();
    if (fopen((NAME+".inp").c_str(), "r")){
        freopen((NAME+".inp").c_str(), "r", stdin);
        freopen((NAME+".out").c_str(), "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while (t--){
        INPUT();
        SOLVE();
    }

    cerr << el << "Time elapsed: " << clock() - start << "ms" << el;
    return 0;
}
// Solution by Dung Vu - Informatics K36 CTN. Solve in 23h09 - 22/08/2025
// My waifu loves her boyfriend. While I'm feeling with my code and waiting for season 2 :>

Compilation message (stderr)

museum.cpp: In function 'int main()':
museum.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen((NAME+".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen((NAME+".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/tmp/ccyn4xPY.o: in function `__tcf_0':
museum.cpp:(.text+0x9): relocation truncated to fit: R_X86_64_PC32 against symbol `adj' defined in .bss section in /tmp/ccyn4xPY.o
/tmp/ccyn4xPY.o: in function `dfs(long long, long long)':
museum.cpp:(.text+0x9e): relocation truncated to fit: R_X86_64_PC32 against symbol `adj' defined in .bss section in /tmp/ccyn4xPY.o
museum.cpp:(.text+0x10a): relocation truncated to fit: R_X86_64_PC32 against symbol `K' defined in .bss section in /tmp/ccyn4xPY.o
/tmp/ccyn4xPY.o: in function `SOLVE()':
museum.cpp:(.text+0x21b): relocation truncated to fit: R_X86_64_PC32 against symbol `N' defined in .bss section in /tmp/ccyn4xPY.o
museum.cpp:(.text+0x288): relocation truncated to fit: R_X86_64_PC32 against symbol `X' defined in .bss section in /tmp/ccyn4xPY.o
museum.cpp:(.text+0x2a2): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
museum.cpp:(.text+0x2a9): relocation truncated to fit: R_X86_64_PC32 against symbol `X' defined in .bss section in /tmp/ccyn4xPY.o
museum.cpp:(.text+0x2b4): relocation truncated to fit: R_X86_64_PC32 against symbol `K' defined in .bss section in /tmp/ccyn4xPY.o
/tmp/ccyn4xPY.o: in function `Rand(long long, long long)':
museum.cpp:(.text+0x2f4): relocation truncated to fit: R_X86_64_PC32 against symbol `rd' defined in .bss section in /tmp/ccyn4xPY.o
museum.cpp:(.text+0x301): relocation truncated to fit: R_X86_64_PC32 against symbol `rd' defined in .bss section in /tmp/ccyn4xPY.o
museum.cpp:(.text+0x325): additional relocation overflows omitted from the output
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1c): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x1c6): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x260): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2e2): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x353): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x541): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5e5): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x670): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x6e9): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
/usr/bin/ld: final link failed
collect2: error: ld returned 1 exit status