oj.uz

Submission #825944

# Submission time Handle Problem Language Result Execution time Memory
825944 2023-08-15T09:28:11 Z fdnfksd Parkovi (COCI22_parkovi) C++14
10 / 110
 1006 ms 37284 KB 
#include <bits/stdc++.h>
#define taskname "cargroup"
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> pli;
typedef unsigned long long ull;
#define fi first
#define se second
#define pb push_back

#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const ll maxN=2e5+10;
// a la thg chon gan nhat
// b la thg ko thoa man xa nhat
ll a[maxN],b[maxN];
const ll inf=1e15;
vector<pli>g[maxN];
#define fi first
#define se second
ll cnt=0;
vector<ll>trace;
bool in[maxN];
void dfs(ll u,ll p,ll mid)
{
    a[u]=inf;
    b[u]=0;
    for(auto vv:g[u])
    {
        int v=vv.fi;
        int w=vv.se;
        if(v==p) continue;
        dfs(v,u,mid);
    }
    for(auto vv:g[u])
    {
        int v=vv.fi;
        int w=vv.se;
        if(v==p) continue;
        if(b[v]+w>mid)
        {
            trace.pb(v);
            in[v]=true;
            cnt++;
            a[v]=0;
            a[u]=min(a[u],w);
            b[v]=-1;
        }
        else
        {
            if(b[v]!=-1) b[u]=max(b[u],b[v]+w);
            a[u]=min(a[u],a[v]+w);
        }
    }
    if(a[u]+b[u]<=mid)
    {
        b[u]=-1;
    }
    if(u==1&&b[1]!=-1)
    {
        cnt++;
        trace.pb(1);
        in[1]=true;
    }
}
ll k,n;
bool check(ll mid)
{
    trace.clear();
    for(int i=1;i<=n;i++) in[i]=false;
    cnt=0;
    dfs(1,0,mid);
    return cnt<=k;
}
//ll n;
void solve()
{
    cin >> n >> k;
    for(int i=1;i<n;i++)
    {
        ll u,v,w;
        cin >> u >> v >> w;
        g[u].pb({v,w});
        g[v].pb({u,w});
    }
    ll low=0,high=3e14;
    while(low<=high)
    {
        ll mid=low+high>>1;
        if(check(mid)) high=mid-1;
        else low=mid+1;
    }
    cout << low<<'\n';
    check(low);
    for(int i=1;i<=n;i++)
    {
        if(in[i]==false&&trace.size()<k) trace.pb(i),in[i]=true;
    }
    for(auto zz:trace) cout << zz<<' ';
}
signed main()
{
    faster
//   freopen(taskname".INP","r",stdin);
//    freopen(taskname".OUT","w",stdout);
    solve();
    return 0;
}

Compilation message

Main.cpp: In function 'void dfs(ll, ll, ll)':
Main.cpp:31:13: warning: unused variable 'w' [-Wunused-variable]
   31 |         int w=vv.se;
      |             ^
Main.cpp: In function 'void solve()':
Main.cpp:89:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |         ll mid=low+high>>1;
      |                ~~~^~~~~
Main.cpp:97:38: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   97 |         if(in[i]==false&&trace.size()<k) trace.pb(i),in[i]=true;
      |                          ~~~~~~~~~~~~^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4944 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Incorrect 2 ms 4948 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 34544 KB Output is correct
2 Correct 333 ms 35344 KB Output is correct
3 Correct 362 ms 19304 KB Output is correct
4 Correct 1006 ms 17732 KB Output is correct
5 Correct 721 ms 17324 KB Output is correct
6 Correct 760 ms 17228 KB Output is correct
7 Correct 909 ms 17436 KB Output is correct
8 Correct 950 ms 18188 KB Output is correct
9 Correct 862 ms 17756 KB Output is correct
10 Correct 876 ms 17996 KB Output is correct
11 Correct 728 ms 19344 KB Output is correct
12 Correct 736 ms 19432 KB Output is correct
13 Correct 702 ms 20772 KB Output is correct
14 Correct 883 ms 19252 KB Output is correct
15 Correct 837 ms 18780 KB Output is correct
16 Correct 760 ms 19556 KB Output is correct
17 Correct 750 ms 18768 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 35892 KB Output is correct
2 Correct 317 ms 35032 KB Output is correct
3 Correct 334 ms 33492 KB Output is correct
4 Correct 317 ms 33420 KB Output is correct
5 Correct 377 ms 37284 KB Output is correct
6 Incorrect 397 ms 36308 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4944 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Incorrect 2 ms 4948 KB Output isn't correct
10 Halted 0 ms 0 KB -