oj.uz

Submission #696686

# Submission time Handle Problem Language Result Execution time Memory
696686 2023-02-07T03:59:07 Z Tuanlinh123 Parkovi (COCI22_parkovi) C++17
10 / 110
 77 ms 16500 KB 
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

#define LOCALIO "C:/Users/admin/Documents/Code/"

ll n, k;
ll dis[200005], deg[100005];
bool print[200005];
vector <pll> Line;
vector <pll> A[200005];
priority_queue <pll, vector <pll>, greater <pll>> q;

ll maxdis(ll mask)
{
    for (ll i=0; i<n; i++)
        dis[i]=1e18;
    for (ll i=0; i<n; i++)
        if (mask&1<<i)
            q.push({0, i}), dis[i]=0;
    while (!q.empty())
    {
        ll u=q.top().se, disu=q.top().fi; q.pop();
        if (dis[u]!=disu)
            continue;
        for (pll child:A[u])
        {
            ll v=child.fi, w=child.se;
            if (dis[v]>disu+w)
            {
                dis[v]=disu+w;
                q.push({dis[v], v});
            }
        }
    }
    ll Max=0;
    for (ll i=0; i<n; i++)
        Max=max(Max, dis[i]);
    return Max;
}

void straighten(ll u, ll pre, ll dis)
{
    Line.pb({u, dis});
    if (deg[u]==1)
        return;
    if (A[u][0].fi==pre)
        straighten(A[u][1].fi, u, A[u][1].se);
    else straighten(A[u][0].fi, u, A[u][0].se);
}

bool check(ll mid)
{
    ll cnt=0, crr=0;
    bool has=0;
    for (ll i=0; i<n; i++)
    {
        if (crr+Line[i].se>mid)
        {
            cnt++, crr=-mid;
            if (!has)
                has=1, crr+=Line[i].se;
        }
        else crr+=Line[i].se;
    }
    if (crr>0) cnt++;
    if (cnt>k) return 0;
    return 1;
}

void trace(ll mid)
{
    ll cnt=0, crr=0;
    bool has=0;
    for (ll i=0; i<n; i++)
    {
        if (crr+Line[i].se>mid)
        {
            cout << Line[i-1].fi+1 << " ";
            print[Line[i-1].fi]=1;
            cnt++; crr=-mid;
            if (!has)
                has=1, crr+=Line[i].se;
        }
        else crr+=Line[i].se;
    }
    if (crr>0) cnt++, cout << Line.back().fi+1 << " ", print[Line.back().se]=1;
    for (ll i=0; i<n; i++)
    {
        if (cnt==k)
            break;
        if (!print[i])
        {
            cnt++;
            cout << i+1 << " ";
        }
    }
}

int main()
{
    #ifdef LOCAL
        freopen( LOCALIO "input.txt","r",stdin) ;
        freopen( LOCALIO "output.txt","w",stdout) ;
    #endif

    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
//	freopen("FIBONACCI.inp","r",stdin);
//	freopen("FIBONACCI.out","w",stdout);
    cin >> n >> k;
    bool line=1;
    for (ll i=1; i<n; i++)
    {
        ll u, v, w; cin >> u >> v >> w;
        u--; v--; deg[u]++; deg[v]++;
        if (deg[u]>2 || deg[v]>2) line=0;
        A[u].pb({v, w}); A[v].pb({u, w});
    }
    if (n<=20)
    {
        pll Min={1e18, 0};
        for (ll mask=0; mask<1<<n; mask++)
            if (__builtin_popcount(mask)==k)
                Min=min(Min, {maxdis(mask), mask});
        cout << Min.fi << "\n";
        for (ll i=0; i<n; i++)
            if (Min.se&1<<i)
                cout << i+1 << " ";
        return 0;
    }
    // if (line)
    // {
    //     ll root=0;
    //     for (ll i=0; i<n; i++)
    //         if (deg[i]==1)
    //             root=i;
    //     Line.pb({root, 0});
    //     straighten(A[root][0].fi, root, A[root][0].se);
    //     ll lo=0, hi=1e15;
    //     while (hi-lo>1)
    //     {
    //         ll mid=(lo+hi)/2;
    //         if (check(mid))
    //             hi=mid;
    //         else lo=mid;
    //     }
    //     if (check(lo))
    //     {
    //         cout << lo << "\n";
    //         trace(lo);
    //     }
    //     else
    //     {
    //         cout << hi << "\n";
    //         trace(hi);
    //     }
    //     return 0;
    // }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:118:10: warning: variable 'line' set but not used [-Wunused-but-set-variable]
  118 |     bool line=1;
      |          ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4948 KB Output is correct
2 Correct 6 ms 4948 KB Output is correct
3 Correct 6 ms 4948 KB Output is correct
4 Correct 5 ms 4948 KB Output is correct
5 Correct 6 ms 5028 KB Output is correct
6 Correct 17 ms 4948 KB Output is correct
7 Correct 21 ms 5036 KB Output is correct
8 Correct 10 ms 5032 KB Output is correct
9 Correct 77 ms 4948 KB Output is correct
10 Correct 10 ms 5024 KB Output is correct
11 Correct 41 ms 5024 KB Output is correct
12 Correct 76 ms 5016 KB Output is correct
13 Correct 6 ms 5032 KB Output is correct
14 Correct 38 ms 4948 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 16108 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 16500 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4948 KB Output is correct
2 Correct 6 ms 4948 KB Output is correct
3 Correct 6 ms 4948 KB Output is correct
4 Correct 5 ms 4948 KB Output is correct
5 Correct 6 ms 5028 KB Output is correct
6 Correct 17 ms 4948 KB Output is correct
7 Correct 21 ms 5036 KB Output is correct
8 Correct 10 ms 5032 KB Output is correct
9 Correct 77 ms 4948 KB Output is correct
10 Correct 10 ms 5024 KB Output is correct
11 Correct 41 ms 5024 KB Output is correct
12 Correct 76 ms 5016 KB Output is correct
13 Correct 6 ms 5032 KB Output is correct
14 Correct 38 ms 4948 KB Output is correct
15 Incorrect 69 ms 16108 KB Unexpected end of file - int64 expected
16 Halted 0 ms 0 KB -