Submission #873960

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

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;

#define For(i,a,b) for(int i=a;i<=b;i++)

typedef vector<int> vi;
#define pb push_back
const int Size=2e5;
const int Maxn=1e6;
const int INF=1<<20;
int ans;
int dp[Maxn+20],sz[Size+20],cnt[Maxn+20];
vector<pii> adj[Size+20];
bitset<Size+20> vis;
void dfs_sz(int u,int pa){
    sz[u]=1;
    for(auto [v,w]:adj[u]){
        if(v==pa||vis[v])   continue;
        dfs_sz(v,u);
        sz[u]+=sz[v];
    }
}
int dfs_cen(int u,int pa,int tot_sz){
    for(auto [v,w]:adj[u]){
        if(v==pa||vis[v])   continue;
        if(sz[v]>(tot_sz>>1))   return dfs_cen(v,u,tot_sz);
    }
    return u;
}
void get_path(int u,int pa,int len,int dep,vi &vec,int K){
    if(len>K)   return ;
    cnt[len]=min(cnt[len],dep);
    ans=min(ans,dp[K-len]+cnt[len]);
    vec.pb(len);
    for(auto [v,w]:adj[u]){
        if(v==pa||vis[v])   continue;
        get_path(v,u,len+w,dep+1,vec);
    }
}
void c_d(int rt,int K){
    dfs_sz(rt,rt);
    int centroid=dfs_cen(rt,rt,sz[rt]);
    vis[centroid]=true;
    vi vec;
    for(auto [v,w]:adj[centroid]){
        if(vis[v])  continue;
        vi vec2;
        get_path(v,centroid,w,1,vec2,K);
        for(auto i:vec2){
            dp[i]=min(dp[i],cnt[i]);
            vec.pb(i);
        }
        for(auto i:vec2)    cnt[i]=INF;
    }
    for(auto i:vec) dp[i]=INF;
    for(auto [v,w]:adj[centroid]){
        if(vis[v])  continue;
        c_d(v,K);
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    For(i,0,N-2){
        int u=H[i][0],v=H[i][1],w=L[i];
        u++,v++;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    ans=INF;
    For(i,1,K)  dp[i]=cnt[i]=INF;
    c_d(1,K);
    return (ans==INF?-1:ans);
}

Compilation message (stderr)

race.cpp:14:8: error: 'pii' was not declared in this scope
   14 | vector<pii> adj[Size+20];
      |        ^~~
race.cpp:14:11: error: template argument 1 is invalid
   14 | vector<pii> adj[Size+20];
      |           ^
race.cpp:14:11: error: template argument 2 is invalid
race.cpp: In function 'void dfs_sz(int, int)':
race.cpp:18:25: error: 'begin' was not declared in this scope
   18 |     for(auto [v,w]:adj[u]){
      |                         ^
race.cpp:18:25: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from race.cpp:2:
/usr/include/c++/10/valarray:1224:5: note:   'std::begin'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from race.cpp:2:
/usr/include/c++/10/bits/fs_dir.h:549:3: note:   'std::filesystem::__cxx11::begin'
  549 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
race.cpp:18:25: error: 'end' was not declared in this scope
   18 |     for(auto [v,w]:adj[u]){
      |                         ^
race.cpp:18:25: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from race.cpp:2:
/usr/include/c++/10/valarray:1244:5: note:   'std::end'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from race.cpp:2:
/usr/include/c++/10/bits/fs_dir.h:554:3: note:   'std::filesystem::__cxx11::end'
  554 |   end(recursive_directory_iterator) noexcept
      |   ^~~
race.cpp: In function 'int dfs_cen(int, int, int)':
race.cpp:25:25: error: 'begin' was not declared in this scope
   25 |     for(auto [v,w]:adj[u]){
      |                         ^
race.cpp:25:25: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from race.cpp:2:
/usr/include/c++/10/valarray:1224:5: note:   'std::begin'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from race.cpp:2:
/usr/include/c++/10/bits/fs_dir.h:549:3: note:   'std::filesystem::__cxx11::begin'
  549 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
race.cpp:25:25: error: 'end' was not declared in this scope
   25 |     for(auto [v,w]:adj[u]){
      |                         ^
race.cpp:25:25: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from race.cpp:2:
/usr/include/c++/10/valarray:1244:5: note:   'std::end'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from race.cpp:2:
/usr/include/c++/10/bits/fs_dir.h:554:3: note:   'std::filesystem::__cxx11::end'
  554 |   end(recursive_directory_iterator) noexcept
      |   ^~~
race.cpp: In function 'void get_path(int, int, int, int, vi&, int)':
race.cpp:36:25: error: 'begin' was not declared in this scope
   36 |     for(auto [v,w]:adj[u]){
      |                         ^
race.cpp:36:25: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from race.cpp:2:
/usr/include/c++/10/valarray:1224:5: note:   'std::begin'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from race.cpp:2:
/usr/include/c++/10/bits/fs_dir.h:549:3: note:   'std::filesystem::__cxx11::begin'
  549 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
race.cpp:36:25: error: 'end' was not declared in this scope
   36 |     for(auto [v,w]:adj[u]){
      |                         ^
race.cpp:36:25: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from race.cpp:2:
/usr/include/c++/10/valarray:1244:5: note:   'std::end'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from race.cpp:2:
/usr/include/c++/10/bits/fs_dir.h:554:3: note:   'std::filesystem::__cxx11::end'
  554 |   end(recursive_directory_iterator) noexcept
      |   ^~~
race.cpp: In function 'void c_d(int, int)':
race.cpp:46:32: error: 'begin' was not declared in this scope
   46 |     for(auto [v,w]:adj[centroid]){
      |                                ^
race.cpp:46:32: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from race.cpp:2:
/usr/include/c++/10/valarray:1224:5: note:   'std::begin'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from race.cpp:2:
/usr/include/c++/10/bits/fs_dir.h:549:3: note:   'std::filesystem::__cxx11::begin'
  549 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
race.cpp:46:32: error: 'end' was not declared in this scope
   46 |     for(auto [v,w]:adj[centroid]){
      |                                ^
race.cpp:46:32: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from race.cpp:2:
/usr/include/c++/10/valarray:1244:5: note:   'std::end'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from race.cpp:2:
/usr/include/c++/10/bits/fs_dir.h:554:3: note:   'std::filesystem::__cxx11::end'
  554 |   end(recursive_directory_iterator) noexcept
      |   ^~~
race.cpp:57:32: error: 'begin' was not declared in this scope
   57 |     for(auto [v,w]:adj[centroid]){
      |                                ^
race.cpp:57:32: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from race.cpp:2:
/usr/include/c++/10/valarray:1224:5: note:   'std::begin'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from race.cpp:2:
/usr/include/c++/10/bits/fs_dir.h:549:3: note:   'std::filesystem::__cxx11::begin'
  549 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
race.cpp:57:32: error: 'end' was not declared in this scope
   57 |     for(auto [v,w]:adj[centroid]){
      |                                ^
race.cpp:57:32: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from race.cpp:2:
/usr/include/c++/10/valarray:1244:5: note:   'std::end'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from race.cpp:2:
/usr/include/c++/10/bits/fs_dir.h:554:3: note:   'std::filesystem::__cxx11::end'
  554 |   end(recursive_directory_iterator) noexcept
      |   ^~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:8:12: error: request for member 'push_back' in 'adj[u]', which is of non-class type 'int'
    8 | #define pb push_back
      |            ^~~~~~~~~
race.cpp:67:16: note: in expansion of macro 'pb'
   67 |         adj[u].pb({v,w});
      |                ^~
race.cpp:8:12: error: request for member 'push_back' in 'adj[v]', which is of non-class type 'int'
    8 | #define pb push_back
      |            ^~~~~~~~~
race.cpp:68:16: note: in expansion of macro 'pb'
   68 |         adj[v].pb({u,w});
      |                ^~