oj.uz

Submission #869081

# Submission time Handle Problem Language Result Execution time Memory
869081 2023-11-03T05:53:36 Z Mr_Ph Parkovi (COCI22_parkovi) C++14
10 / 110
 1034 ms 52228 KB 
#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
typedef long long int lli;
typedef unsigned long long ull;
using namespace std;
using namespace __gnu_pbds;
template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
ll mod=(ll)1e9+7;
ll mod1=998244353;
///the defines :)
#define endl '\n'
#define vi vector<int>
#define vll vector<ll>
#define ent(arr) for(int i=0;i<arr.size();i++)cin>>arr[i];
#define all(arr) arr.begin(),arr.end()
#define allr(arr) arr.rbegin(),arr.rend()
#define sz size()
#define int long long
vector<vector<pair<int,int>>>adj;
vector<int>cpark;
vector<int>fpark;
int curk;
vi xd;
void dfs(int node,int parent,int mid,int prv)
{
    for(auto i:adj[node])
    {
		if (i.first == parent) continue;
			dfs(i.first,node,mid,i.second);
			cpark[node]=min(cpark[node],cpark[i.first]+i.second);
			fpark[node]=max(fpark[node],fpark[i.first]+i.second);
	}
	if(cpark[node]>mid)
        fpark[node]=max(0ll,fpark[node]);
	if(fpark[node]+cpark[node]<=mid){
	    fpark[node]=-1e15;
		return;
	}
	if (fpark[node]+prv>mid)
	{
		xd.push_back(node);
		curk++;
		fpark[node]=-1e15;
		cpark[node]=0;
	}
    else if(node==1&&fpark[node]>=0)
    {
        curk++;
        xd.push_back(node);
    }
}
void preprocess() {}
void solve()
{
    int n,k;
    cin>>n>>k;
    adj.resize(n+1);
    cpark.resize(n+1);
    fpark.resize(n+1);
    for(int i=1; i<n; i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    int l=1,r=1e15;
    int ans=0;
    vi ans1;
    vi lol;
    while(l<=r)
    {
        int mid=(l+r)/2;
        curk=0;
        xd=lol;
        for(int i=1; i<=n; i++)
            cpark[i]=1e15,fpark[i]=-1e15;
        dfs(1,0,mid,0);
        if(curk<=k)
        {
            ans=mid;
            ans1=xd;
            r=mid-1;
        }
        else
            l=mid+1;
    }
     for(int i=1; i<=n; i++)
            cpark[i]=1e15,fpark[i]=-1e15;
    curk=0;
    xd.clear();
    cout<<ans<<endl;
    dfs(1,0,ans,0);
    ans1=xd;
    map<int,int>mp;
    int cnt=ans1.sz;
    for(auto i:ans1)cout<<i<<" ";
    for(int i=1; i<=n; i++)
    {
        if(!mp[i]&&cnt<k)
        {
            cnt++;
            cout<<i<<" ";
        }
    }
    cout<<endl;
}
signed main()
{
    // freopen("meta_game_input.txt","r",stdin);
    // freopen("otput.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    preprocess();
    //bla();
    int t=1;
    //cin>>t;
    while(t--)
        solve();
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 42828 KB Output is correct
2 Correct 341 ms 48556 KB Output is correct
3 Correct 349 ms 34496 KB Output is correct
4 Correct 802 ms 33076 KB Output is correct
5 Correct 800 ms 32340 KB Output is correct
6 Correct 839 ms 32092 KB Output is correct
7 Correct 775 ms 31020 KB Output is correct
8 Correct 1020 ms 32852 KB Output is correct
9 Correct 1034 ms 32480 KB Output is correct
10 Correct 961 ms 33300 KB Output is correct
11 Correct 682 ms 34824 KB Output is correct
12 Correct 567 ms 33904 KB Output is correct
13 Correct 803 ms 37200 KB Output is correct
14 Correct 640 ms 32852 KB Output is correct
15 Correct 599 ms 32000 KB Output is correct
16 Correct 589 ms 33792 KB Output is correct
17 Correct 651 ms 32752 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 44700 KB Output is correct
2 Correct 323 ms 47920 KB Output is correct
3 Correct 308 ms 45452 KB Output is correct
4 Correct 297 ms 45396 KB Output is correct
5 Correct 399 ms 51060 KB Output is correct
6 Correct 406 ms 49644 KB Output is correct
7 Correct 429 ms 51740 KB Output is correct
8 Correct 353 ms 48824 KB Output is correct
9 Correct 350 ms 48316 KB Output is correct
10 Correct 392 ms 47444 KB Output is correct
11 Correct 321 ms 45756 KB Output is correct
12 Incorrect 406 ms 52228 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -