Submission #949398

#	Time	Username	Problem	Language	Result	Execution time	Memory
949398		Yang8on	Parkovi (COCI22_parkovi)	C++14	110 / 110	1638 ms	39132 KiB

Main

#include <bits/stdc++.h>

#define Yang8on Nguyen_Dinh_Son
#define sonphamay Nguyen_Dinh_Son

#define aothtday "aog"
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define ll long long
#define endl '\n'
#define pii pair<int, ll>
#define pb push_back
#define all(v) v.begin(), v.end()
#define f first
#define s second
#define maxn 200005
#define maxm
#define maxx
#define mod 1000000007
#define base 311
#define ModHas 1000000003ll
#define gb(i, j) ((i >> j) & 1)
#define int long long

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rng);
}

const ll oo = 1e18;

int n, k;
ll lim, sl;
ll dis[maxn], reach[maxn], place[maxn];
vector<pii> o[maxn];
/// reach[u] : khoảng cách xa nhất đến 1 đỉnh chưa được bao phủ (gọi đỉnh đấy là u, tức u đến 1 đỉnh
void dfs(int u, int par)
{
    for(pii x : o[u])
    {
        int v = x.f;
        ll w = x.s;

        if(v == par) continue;

        dfs(v, u);

        if(reach[v] + min(w, dis[v]) <= lim) /// (**)
        {
            if(reach[v] + dis[v] > lim) reach[u] = max(reach[u], reach[v] + w);
            dis[u] = min(dis[u], dis[v] + w);
        }
        else
        {
            place[v] = 1, sl ++;
            dis[u] = min(dis[u], w);
        }
    }
}

bool calc(int mid)
{
    fi(i, 1, n) dis[i] = oo, reach[i] = 0, place[i] = 0;

    lim = mid, sl = 0;
    dfs(1, -1);

    if(dis[1] + reach[1] > lim) place[1] = 1, sl ++;

    if(sl > k) return false;
    return true;
}

/// (**): tại sao lại là reach[v] + min(w, dis[v]) chứ không phải reach[v] + dis[v]?

/// nếu reach[v] + min(w, dis[v]) <= lim, tức đến u, nếu reach[v] + dis[v] > lim
/// --> reach[v] sẽ ko được điểm đánh dấu nào bao phủ nữa, thay vào đó ta sẽ tìm đình xa
/// nhất có thể đặt để bao phủ v, khi đó điểm đặt của ta sẽ men theo đường từ v lên u
/// --> từ đấy mà có reach[v] + w <= lim --> vẫn có thể chờ để đặt đỉnh tối ưu hơn, tăng
/// reach[u] lên

void solve()
{
    cin >> n >> k;
    fi(i, 1, n - 1)
    {
        int x, y;
        ll w;
        cin >> x >> y >> w;
        o[x].pb({y, w});
        o[y].pb({x, w});
    }

    int l = 0, r = oo;
    while(l <= r)
    {
        int mid = (l + r) >> 1;

        if(calc(mid)) r = mid - 1;
        else l = mid + 1;
    }

    bool check = calc(l);
    sl = 0;
    fi(i, 1, n) if(place[i]) sl ++;

    cout << l << '\n';

    fi(i, 1, n)
    {
        if(place[i]) cout << i << ' ';
        else if(sl < k) sl ++, cout << i << ' ';
    }
}

signed main()
{
    if(fopen(aothtday".inp", "r"))
    {
        freopen(aothtday".inp","r",stdin);
        freopen(aothtday".out","w",stdout);
    }

    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int nTest = 1;
//    cin >> nTest;

    while(nTest --)
    {
        solve();
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:107:10: warning: unused variable 'check' [-Wunused-variable]
  107 |     bool check = calc(l);
      |          ^~~~~
Main.cpp: In function 'int main()':
Main.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(aothtday".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(aothtday".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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