Submission #865973

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

race

#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
//Don't open the standings during contests.
const int mxn=2e5+5;
vector<pii>adj[mxn];
int cnt[mxn];
bool vis[mxn];
void cnt_sz(int v,int pa){
    cnt[v]=1;
    for(auto [u,d]:adj[v]){
        if(vis[u] or u==pa)continue;
        cnt_sz(u,v);
        cnt[v]+=cnt[u];
    }
}
int find(int v,int pa,int tar){
    for(auto [u,d]:adj[v]){
        if(vis[u] or u==pa)continue;
        if(cnt[u]*2>tar)return find(u,v,tar);
    }
    return v;
}
int ans=8e10;
vector<pii>dis;
void dfs(int v,int pa,int l,int len,int k){
    //cout<<v<<' '<<l<<' '<<len<<'\n';
    if(l>k)return;
    dis.pb({l,len});
    for(auto [u,d]:adj[v]){
        if(vis[u] or u==pa)continue;
        dfs(u,v,l+1,len+d,k);
    }
}
int f[mxn];
void cd(int v,int k,int n){
    cnt_sz(v,v);
    v=find(v,v,cnt[v]);
    vis[v]=1;
    vector<int>undo;
    for(auto [u,d]:adj[v]){
        if(vis[u])continue;
        dis.clear();
        dis.pb({0,0});
        dfs(u,v,1,d,k);
        for(int j=0;j<sz(dis);j++){
            chmin(ans,f[k-dis[j].S]+dis[j].F);
           // cout<<u<<' '<<dis[j].S<<' '<<dis[j].F<<' '<<f[k-dis[j].S]<<' '<<ans<<'\n';
        }
        for(int j=0;j<sz(dis);j++){
            undo.pb(dis[j].S);
            chmin(f[dis[j].S],dis[j].F);
        }
    }
    for(auto x:undo)f[x]=8e10;
    for(auto [u,d]:adj[v]){
        if(vis[u])continue;
        cd(u,k,n);
    }
}
int best_path(int n,int k,int h[][2],int l[]){
    for(int i=0;i<n-1;i++){
        adj[h[i][0]].pb({h[i][1],l[i]});
        adj[h[i][1]].pb({h[i][0],l[i]});
    }
    for(int i=0;i<=k;i++){
        f[i]=8e10;
    }
    cd(0,k,n);
    return (ans==8e10?-1:ans);
}
 /*
 input:
  11 12
  0 1
  0 2
  2 3
  3 4
  4 5
  0 6
  6 7
  6 8
  8 9
  8 10
  3
  4
  5
  4
  6
  3
  2
  5
  6
  7
*/

Compilation message (stderr)

race.cpp: In function 'void cnt_sz(long long int, long long int)':
race.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |     for(auto [u,d]:adj[v]){
      |              ^
race.cpp: In function 'long long int find(long long int, long long int, long long int)':
race.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for(auto [u,d]:adj[v]){
      |              ^
race.cpp: In function 'void dfs(long long int, long long int, long long int, long long int, long long int)':
race.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for(auto [u,d]:adj[v]){
      |              ^
race.cpp: In function 'void cd(long long int, long long int, long long int)':
race.cpp:53:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |     for(auto [u,d]:adj[v]){
      |              ^
race.cpp:68:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |     for(auto [u,d]:adj[v]){
      |              ^
/usr/bin/ld: /tmp/ccf8h2wC.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