Submission #386084

#	Time	Username	Problem	Language	Result	Execution time	Memory
386084		cpp219	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 2e5 + 6;
const ll Log2 = 19;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
vector<LL> g[N];
ll n,k,w[N],H[N][2],child[N],len[N],d[N],ans = inf,L[N],centroid;
bool Is_cent[N];
multiset<LL> All;

ll Find_cent(ll u,ll p,ll total){
    for (auto i : g[u]){
        ll v = i.fs,now = i.sc;
        if (!Is_cent[v]&&v != p&&child[v]*2 > total) return Find_cent(v,u,total);
    }
    Is_cent[u] = 1; return u;
}

void reDFS(ll u,ll p){
    child[u] = 1;
    for (auto i : g[u]){
        ll v = i.fs,now = i.sc;
        if (!Is_cent[v] && v != p){
            len[v] = len[u] + now;  d[v] = d[u] + 1;
            reDFS(v,u); child[u] += child[v];
        }
    }
}

void Add(ll u,ll p){
    All.insert({len[u],d[u]});
    for (auto i : g[u]){
        ll v = i.fs;
        if (!Is_cent[v] && v != p) Add(v,u);
    }
}

void Delete(ll u,ll p){
    auto it = All.find({len[u],d[u]});
    All.erase(it);
    for (auto i : g[u]){
        ll v = i.fs;
        if (!Is_cent[v] && v != p) Delete(v,u);
    }
}

void out(){
    for (auto i : All) cout<<i.fs<<" "<<i.sc<<"\n"; exit(0);
}

void update(ll u,ll p){
    if (len[u] == k) ans = min(ans,d[u]);
    if (len[u] < k){
        auto now = All.lower_bound({k - len[u],0});
        LL it = *now; //cout<<it.fs<<" "<<k <<" "<< len[u]; exit(0);
        if (now != All.end()&&it.fs == k - len[u]){
            ans = min(ans,it.sc + d[u]);
        }
        //if (u == 8&&centroid == 10) cout<<it.fs<<"x\n",out();
    }
    for (auto i : g[u]){
        ll v = i.fs;
        if (!Is_cent[v] && v != p) update(v,u);
    }
}

void DFS(ll u){
    reDFS(u,0); All.clear();
    centroid = Find_cent(u,0,child[u]); len[centroid] = 0; d[centroid] = 0;
    reDFS(centroid,0);
    for (auto i : g[centroid]){
        ll v = i.fs;
        if (!Is_cent[v]) Add(v,centroid);
    }
    for (auto i : g[centroid]){
        ll v = i.fs;
        if (!Is_cent[v]){
            Delete(v,centroid);
            update(v,centroid); Add(v,centroid);
        }
    }
    //cout<<centroid<<" x "<<ans; exit(0);
    for (auto i : g[centroid]){
        ll v = i.fs;
        if (!Is_cent[v]) DFS(v);
    }
}

ll best_path(ll num,ll K,ll H[][2],ll L[]){
    n = num; k = K;
    for (ll i = 0;i < n - 1;i++){
        ll x = H[i][0],y = H[i][1]; x++; y++;
        g[x].push_back({y,L[i]}); g[y].push_back({x,L[i]});
    }
    DFS(1);
    if (ans != inf) return ans;
    return -1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "test"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>n>>k;
    for (ll i = 0;i < n - 1;i++) cin>>H[i][0]>>H[i][1]>>L[i];
    cout<<best_path(n,k,H,L);
}

Compilation message (stderr)

race.cpp: In function 'int Find_cent(int, int, int)':
race.cpp:18:21: warning: unused variable 'now' [-Wunused-variable]
   18 |         ll v = i.fs,now = i.sc;
      |                     ^~~
race.cpp: In function 'void out()':
race.cpp:53:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   53 |     for (auto i : All) cout<<i.fs<<" "<<i.sc<<"\n"; exit(0);
      |     ^~~
race.cpp:53:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   53 |     for (auto i : All) cout<<i.fs<<" "<<i.sc<<"\n"; exit(0);
      |                                                     ^~~~
race.cpp: In function 'int main()':
race.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  110 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/tmp/ccEc1QkX.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccXBdDl1.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status