Submission #1099302

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1099302	2024-10-11T06:47:43 Z	m5588ohammed	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

#include <bits/stdc++.h>
using namespace std;
#define MAX_N 300000
long long n,k,val=0;
long long ans=1e7;
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]);
    nodes[i].insert({0-cnst1[x],0-cnst2[x]});
    long long co=c,le=1;
    auto it=nodes[i].lower_bound({(long long)k-cnst1[x]-co,-10000000ll});
    if(it!=nodes[i].end()&&(*it)[0]==(long long)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;

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

        for(auto [cost,len]:nodes[j]){
            co=cost+cnst1[j]+w,le=len+cnst2[j]+1;
            it=nodes[i].lower_bound({(long long)k-cnst1[i]-co,-10000000ll});
            if(it!=nodes[i].end()&&(*it)[0]==(long long)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]});
        if(L[i]==k) return 1;
    }
    dfs(1,0);
    if(ans!=1e7) 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

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:33:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |     for(auto [j,w]:v[i]){
      |              ^
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:50:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |         for(auto [cost,len]:nodes[j]){
      |                  ^
race.cpp: In function 'int main()':
race.cpp:79:9: warning: unused variable 'solution' [-Wunused-variable]
   79 |     int solution;
      |         ^~~~~~~~
race.cpp: In function 'void dfs(long long int, long long int)':
race.cpp:27:56: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |     auto it=nodes[i].lower_bound({(long long)k-cnst1[x]-co,-10000000ll});
      |                                   ~~~~~~~~~~~~~~~~~~~~~^~~
race.cpp:14:15: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   14 |     long long x,siz=0,c;
      |               ^
/usr/bin/ld: /tmp/ccoqlB1Y.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc6oglqX.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status