제출 #873959

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
873959		CYhuang	Race (IOI11_race)	C++17	컴파일 에러	0 ms	0 KiB

race

#include "race.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);
}

컴파일 시 표준 에러 (stderr) 메시지

race.cpp:6:9: error: 'vector' does not name a type
    6 | typedef vector<int> vi;
      |         ^~~~~~
race.cpp:13:1: error: 'vector' does not name a type
   13 | vector<pii> adj[Size+20];
      | ^~~~~~
race.cpp:14:1: error: 'bitset' does not name a type
   14 | bitset<Size+20> vis;
      | ^~~~~~
race.cpp: In function 'void dfs_sz(int, int)':
race.cpp:17:20: error: 'adj' was not declared in this scope
   17 |     for(auto [v,w]:adj[u]){
      |                    ^~~
race.cpp:18:19: error: 'vis' was not declared in this scope
   18 |         if(v==pa||vis[v])   continue;
      |                   ^~~
race.cpp: In function 'int dfs_cen(int, int, int)':
race.cpp:24:20: error: 'adj' was not declared in this scope
   24 |     for(auto [v,w]:adj[u]){
      |                    ^~~
race.cpp:25:19: error: 'vis' was not declared in this scope
   25 |         if(v==pa||vis[v])   continue;
      |                   ^~~
race.cpp: At global scope:
race.cpp:30:44: error: 'vi' has not been declared
   30 | void get_path(int u,int pa,int len,int dep,vi &vec,int K){
      |                                            ^~
race.cpp: In function 'void get_path(int, int, int, int, int&, int)':
race.cpp:32:14: error: 'min' was not declared in this scope
   32 |     cnt[len]=min(cnt[len],dep);
      |              ^~~
race.cpp:7:12: error: request for member 'push_back' in 'vec', which is of non-class type 'int'
    7 | #define pb push_back
      |            ^~~~~~~~~
race.cpp:34:9: note: in expansion of macro 'pb'
   34 |     vec.pb(len);
      |         ^~
race.cpp:35:20: error: 'adj' was not declared in this scope
   35 |     for(auto [v,w]:adj[u]){
      |                    ^~~
race.cpp:36:19: error: 'vis' was not declared in this scope
   36 |         if(v==pa||vis[v])   continue;
      |                   ^~~
race.cpp: In function 'void c_d(int, int)':
race.cpp:43:5: error: 'vis' was not declared in this scope
   43 |     vis[centroid]=true;
      |     ^~~
race.cpp:44:5: error: 'vi' was not declared in this scope
   44 |     vi vec;
      |     ^~
race.cpp:45:20: error: 'adj' was not declared in this scope
   45 |     for(auto [v,w]:adj[centroid]){
      |                    ^~~
race.cpp:47:11: error: expected ';' before 'vec2'
   47 |         vi vec2;
      |           ^~~~~
      |           ;
race.cpp:48:33: error: 'vec2' was not declared in this scope
   48 |         get_path(v,centroid,w,1,vec2,K);
      |                                 ^~~~
race.cpp:50:19: error: 'min' was not declared in this scope
   50 |             dp[i]=min(dp[i],cnt[i]);
      |                   ^~~
race.cpp:51:13: error: 'vec' was not declared in this scope
   51 |             vec.pb(i);
      |             ^~~
race.cpp:55:16: error: 'vec' was not declared in this scope
   55 |     for(auto i:vec) dp[i]=INF;
      |                ^~~
race.cpp:56:20: error: 'adj' was not declared in this scope
   56 |     for(auto [v,w]:adj[centroid]){
      |                    ^~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:66:9: error: 'adj' was not declared in this scope
   66 |         adj[u].pb({v,w});
      |         ^~~