Submission #1099166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099166		m5588ohammed	Race (IOI11_race)	C++14	9 / 100	86 ms	31312 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define MAX_N 300000
int n,k;
long long ans=1e6;
long long cnst1[MAX_N],cnst2[MAX_N];
vector <array<long long,2>> v[MAX_N];
set <array<long long,2>> nodes[MAX_N];
void dfs(long long i,long long last){
    if(v[i].size()==1&&i!=1){
        nodes[i].insert({0,0});
        return;
    }
    long long x,siz=0,c;
    for(auto [j,w]:v[i]){
        if(j==last) continue;
        dfs(j,i);
        if(nodes[j].size()>siz){
            siz=nodes[j].size();
            x=j;
            c=w;
        }
    }

    swap(nodes[i],nodes[x]);
    long long co=c,le=1;
    auto it=nodes[i].lower_bound({k-cnst1[x]-co,-1000000});
    if(it!=nodes[i].end()&&(*it)[0]==k-cnst1[x]-co){
        ans=min(ans,le+(*it)[1]+cnst2[x]);
    }
    cnst1[i]=cnst1[x]+c,cnst2[i]=cnst2[x]+1;
    nodes[i].insert({co-cnst1[i],le-cnst2[i]});

    for(auto [j,w]:v[i]){
        if(j==last||j==x) continue;
        for(auto [cost,len]:nodes[j]){
            co=cost+cnst1[j]+w,le=len+cnst2[j]+1;
            auto it=nodes[i].lower_bound({k-cnst1[i]-co,-1000000});
            if(it!=nodes[i].end()&&(*it)[0]==k-cnst1[i]-co){
                ans=min(ans,le+(*it)[1]+cnst2[i]);
            }
        }
        for(auto [cost,len]:nodes[j]){
            co=cost+cnst1[j]+w,le=len+cnst2[j]+1;
            nodes[i].insert({co-cnst1[i],le-cnst2[i]});
        }
        nodes[j].clear();
    }
    return;
}
int best_path(int N, int K, int H[][2], int L[])
{
    n=N;
    k=K;
    for(int i=0;i<n-1;i++){
        v[H[i][0]+1].push_back({H[i][1]+1,L[i]});
        v[H[i][1]+1].push_back({H[i][0]+1,L[i]});
    }
    dfs(1,0);
    if(ans!=1e6) return (int)ans;
    else return -1;
}
// signed main()
// {
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);
//     cout.tie(NULL);
//     int N, K;
//     int H[MAX_N][2];
//     int L[MAX_N];
//     int solution;
//     cin>>N>>K;
//     for(int i=0;i<N-1;i++) cin>>H[i][0]>>H[i][1]>>L[i];
//     cout<<best_path(N,K,H,L)<<endl;
//     return 0;
// }

Compilation message (stderr)

race.cpp: In function 'void dfs(long long int, long long int)':
race.cpp:15:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   15 |     for(auto [j,w]:v[i]){
      |              ^
race.cpp:18:27: warning: comparison of integer expressions of different signedness: 'std::set<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   18 |         if(nodes[j].size()>siz){
      |            ~~~~~~~~~~~~~~~^~~~
race.cpp:34:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |     for(auto [j,w]:v[i]){
      |              ^
race.cpp:36:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |         for(auto [cost,len]:nodes[j]){
      |                  ^
race.cpp:43:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |         for(auto [cost,len]:nodes[j]){
      |                  ^
race.cpp:31:22: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |     cnst1[i]=cnst1[x]+c,cnst2[i]=cnst2[x]+1;
      |              ~~~~~~~~^~
race.cpp:14:15: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   14 |     long long x,siz=0,c;
      |               ^

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57