Submission #1059461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059461		Flan312	Parkovi (COCI22_parkovi)	C++17	110 / 110	321 ms	35368 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define task "CONGVIEN"
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
#define fi first
#define se second
#define pii pair <int, int>
#define tii tuple <int, int, int>
#define all(s) s.begin(), s.end()
using namespace std;

const ll oo = 1e18;
const int nmax = 2e5 + 2;
int n, k;
bool placed_park[nmax];
vector <pii> adj[nmax];
ll r = 0;

int cnt = 0;
ll dist[nmax], reach[nmax];
void dfs(int u, int par, ll mxDist)
{
    dist[u] = oo;
    reach[u] = 0;

    for (auto &[v, w] : adj[u])
    {
        if (v == par) continue;
        dfs(v, u, mxDist);

        if (reach[v] + min(1ll * w, dist[v]) <= mxDist) 
        {
            placed_park[v] = 0;
            if (reach[v] + dist[v] > mxDist)
                reach[u] = max(reach[u], reach[v] + w);
            dist[u] = min(dist[u], dist[v] + w);
        }
        else
        {
            placed_park[v] = 1;
            ++cnt;
            dist[u] = min(dist[u], 1ll * w);
        }
    }
}

bool check(ll mxDist)
{
    cnt = 0;
    dfs(1, -1, mxDist);
    if (reach[1] + dist[1] <= mxDist)
        placed_park[1] = 0;
    else
    {
        placed_park[1] = 1;
        ++cnt;
    }
    return cnt <= k;
}

int main()
{
    if (ifstream(task".inp")) nx
    fast

    cin >> n >> k;
    for (int u, v, w, i = 1; i < n; ++i)
    {
        cin >> u >> v >> w;
        adj[u].eb(v, w);
        adj[v].eb(u, w);
        r += w;
    }

    ll l = 0, ans = -1;
    while(l <= r)
    {
        ll mid = l + r >> 1;
        if (check(mid))
            ans = mid, r = mid - 1;
        else l = mid + 1;
    }

    cout << ans << '\n';
    check(ans);
    vector <int> res;
    for (int i = 1; i <= n; ++i)
        if (placed_park[i]) res.eb(i);
    for (int i = 1; i <= n; ++i)
        if (res.size() < k && !placed_park[i]) res.eb(i);
    for (auto &i : res)
        cout << i << ' ';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:81:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |         ll mid = l + r >> 1;
      |                  ~~^~~
Main.cpp:93:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   93 |         if (res.size() < k && !placed_park[i]) res.eb(i);
      |             ~~~~~~~~~~~^~~
Main.cpp:7:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:66:31: note: in expansion of macro 'nx'
   66 |     if (ifstream(task".inp")) nx
      |                               ^~
Main.cpp:7:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:66:31: note: in expansion of macro 'nx'
   66 |     if (ifstream(task".inp")) nx
      |                               ^~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60