Submission #495699

#	Time	Username	Problem	Language	Result	Execution time	Memory
495699		amsminn	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}

int N,K,ans=1e9;
int sz[202020];
int del[202020];
int mp[1010101];
vector<pi>v[202020];
vector<int>D;

int getsize(int x,int p=0){
    sz[x]=1;
    for(auto&[i,j]:v[x])if(i!=p and !del[i])sz[x]+=getsize(i,x);
    return sz[x];
}

int getCent(int x,int p,int cap){
    for(auto&[i,j]:v[x])if(i!=p and !del[i] and sz[i]*2>cap)
        return getCent(i,x,cap);
    return x;
}

void qry(int x,int p,int dist,int dep){
    if(dist>K)return;
    if(mp[K-dist]!=-1 and mp[K-dist]+dep<ans)ans=mp[K-dist]+dep;
    for(auto&[i,j]:v[x])if(i!=p and !del[i])qry(i,x,dist+j,dep+1);
}

void upd(int x,int p,int dist,int dep){
    if(dist>K)return;
    D.pb(dist);
    if(mp[dist]==-1)mp[dist]=dep;
    else if(dep<mp[dist])mp[dist]=dep;
    for(auto&[i,j]:v[x])if(i!=p and !del[i])upd(i,x,dist+j,dep+1);
}

void dnc(int x){
    int cap=getsize(x,0);
    int cent=getCent(x,0,cap);
    del[x]=1;mp[0]=0;
    for(auto&[i,j]:v[x])if(!del[i]){
        qry(i,cent,j,1);
        upd(i,cent,j,1);
    }
    for(auto&i:D)mp[i]=-1;D.clear();
    for(auto&[i,j]:v[x])if(!del[i])dnc(i);
}

#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
int z[36];
char*c=(char*)mmap(0,z[12],1,2,0,fstat(0,(struct stat *)z));
inline int f(){int x=0;bool e;c+=e=*c=='-';while(*c>='0')x=10*x+*c++-'0';c++;return e?-x:x;}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    N=f();K=f();
    for(int i=1;i<=N-1;i++){
        int p=f(),q=f(),r=f();++p;++q;
        v[p].pb({q,r});
        v[q].pb({p,r});
    }
    memset(mp,-1,sizeof mp);
    dnc(1);
    if(ans==1e9)cout<<-1<<endl;
    else cout<<ans<<endl;
}

Compilation message (stderr)

race.cpp: In function 'void dnc(int)':
race.cpp:57:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   57 |     for(auto&i:D)mp[i]=-1;D.clear();
      |     ^~~
race.cpp:57:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   57 |     for(auto&i:D)mp[i]=-1;D.clear();
      |                           ^
/usr/bin/ld: /tmp/ccZKbr55.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc6cFTJ6.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc6cFTJ6.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status