제출 #238215

#제출 시각아이디문제언어결과실행 시간메모리
238215T0p_경주 (Race) (IOI11_race)C++14
컴파일 에러
0 ms0 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #define pb push_back struct EDGE { int node, weight; }; int k, ans = 1e9; int sz[200002], pa[200002], jmp[2][20][200002]; bool visit[200002]; vector<EDGE> g[200002]; map<int, int> mp[200002]; int get_sz(int u, int p) { sz[u] = 1; for(auto x : g[u]) { if(visit[x.node] || x.node == p) continue ; sz[u] += get_sz(x.node, u); } return sz[u]; } int get_centroid(int u, int p, int n) { bool ch = (n - sz[u] <= n/2) ? true : false; int nn = 0, nf = 0; for(auto x : g[u]) { if(visit[x.node] || x.node == p) continue ; if(sz[x.node] > n/2) { ch = false; if(sz[x.node] > nf) { nn = x.node; nf = sz[x.node]; } } } return (ch) ? u : get_centroid(nn, u, n); } int build(int u, int p) { int c = get_centroid(u, p, get_sz(u, p)); visit[c] = true; for(auto x : g[c]) { if(visit[x.node]) continue ; pa[build(x.node, c)] = c; } return c; } void dfs(int u, int l) { lv[u] = l; for(auto x : g[u]) { if(lv[x.node]) continue ; jmp[0][0][x.node] = u; jmp[1][0][x.node] = x.weight; dfs(x.node, l+1); } } int finddis(int u, int v) { int r1 = 0, r2 = 0; if(lv[u] < lv[v]) swap(u, v); for(int i=19 ; i>=0 ; i--) if(lv[jmp[0][i][u]] >= lv[v]) { r1 += (1<<i); r2 += jmp[1][i][u]; u = jmp[1][i][u]; } if(u == v) return {r1, r2}; for(int i=19 ; i>=0 ; i--) if(jmp[0][i][u] != jmp[0][i][v]) { r1 += (1<<(i+1)); r2 += jmp[1][i][u] + jmp[1][i][v]; u = jmp[0][i][u], v = jmp[0][i][v]; } return {r1+2, r2+jmp[1][0][u]+jmp[1][0][v]}; } void update(int u) { int _u = u; while(true) { pair<int, int> dis = finddis(u, _u); if(mp[_u].count(k - dis.second)) ans = min(ans, mp[_u][k-dis.second] + dis.first); mp[_u].count(dis.second) ? mp[_u][dis.second] = min(mp[_u][dis.second], dis.first) : mp[_u][dis.second] = dis.first; _u = pa[_u]; if(!_u) break ; } } int best_path(int N, int K, int H[][2], int L[]) { k = K; for(int i=0 ; i<N-1 ; i++) { g[H[i][0]+1].pb({g[H[i][1]+1], L[i]}); g[H[i][1]+1].pb({g[H[i][0]+1], L[i]}); } dfs(1, 1); build(1, 0); for(int i=1 ; i<20 ; i++) for(int j=1 ; j<=N ; j++) { jmp[0][i][j] = jmp[0][i-1][jmp[0][i-1][j]]; jmp[1][i][j] = jmp[1][i-1][j] + jmp[1][i-1][jmp[0][i-1][j]]; } for(int i=1 ; i<=n ; i++) update(i); return (ans == 1e9) ? -1 : ans; }

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

race.cpp: In function 'void dfs(int, int)':
race.cpp:63:2: error: 'lv' was not declared in this scope
  lv[u] = l;
  ^~
race.cpp:63:2: note: suggested alternative: 'l'
  lv[u] = l;
  ^~
  l
race.cpp: In function 'int finddis(int, int)':
race.cpp:76:5: error: 'lv' was not declared in this scope
  if(lv[u] < lv[v]) swap(u, v);
     ^~
race.cpp:76:5: note: suggested alternative: 'v'
  if(lv[u] < lv[v]) swap(u, v);
     ^~
     v
race.cpp:78:6: error: 'lv' was not declared in this scope
   if(lv[jmp[0][i][u]] >= lv[v])
      ^~
race.cpp:78:6: note: suggested alternative: 'v'
   if(lv[jmp[0][i][u]] >= lv[v])
      ^~
      v
race.cpp:84:27: error: cannot convert '<brace-enclosed initializer list>' to 'int' in return
  if(u == v) return {r1, r2};
                           ^
race.cpp:92:44: error: cannot convert '<brace-enclosed initializer list>' to 'int' in return
  return {r1+2, r2+jmp[1][0][u]+jmp[1][0][v]};
                                            ^
race.cpp: In function 'void update(int)':
race.cpp:100:31: error: conversion from 'int' to non-scalar type 'std::pair<int, int>' requested
   pair<int, int> dis = finddis(u, _u);
                        ~~~~~~~^~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:113:39: error: no matching function for call to 'std::vector<EDGE>::push_back(<brace-enclosed initializer list>)'
   g[H[i][0]+1].pb({g[H[i][1]+1], L[i]});
                                       ^
In file included from /usr/include/c++/7/vector:64:0,
                 from /usr/include/c++/7/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
                 from race.cpp:2:
/usr/include/c++/7/bits/stl_vector.h:939:7: note: candidate: void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = EDGE; _Alloc = std::allocator<EDGE>; std::vector<_Tp, _Alloc>::value_type = EDGE]
       push_back(const value_type& __x)
       ^~~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:939:7: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type& {aka const EDGE&}'
/usr/include/c++/7/bits/stl_vector.h:953:7: note: candidate: void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = EDGE; _Alloc = std::allocator<EDGE>; std::vector<_Tp, _Alloc>::value_type = EDGE]
       push_back(value_type&& __x)
       ^~~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:953:7: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<EDGE>::value_type&& {aka EDGE&&}'
race.cpp:114:39: error: no matching function for call to 'std::vector<EDGE>::push_back(<brace-enclosed initializer list>)'
   g[H[i][1]+1].pb({g[H[i][0]+1], L[i]});
                                       ^
In file included from /usr/include/c++/7/vector:64:0,
                 from /usr/include/c++/7/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
                 from race.cpp:2:
/usr/include/c++/7/bits/stl_vector.h:939:7: note: candidate: void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = EDGE; _Alloc = std::allocator<EDGE>; std::vector<_Tp, _Alloc>::value_type = EDGE]
       push_back(const value_type& __x)
       ^~~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:939:7: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type& {aka const EDGE&}'
/usr/include/c++/7/bits/stl_vector.h:953:7: note: candidate: void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = EDGE; _Alloc = std::allocator<EDGE>; std::vector<_Tp, _Alloc>::value_type = EDGE]
       push_back(value_type&& __x)
       ^~~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:953:7: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<EDGE>::value_type&& {aka EDGE&&}'
race.cpp:124:19: error: 'n' was not declared in this scope
  for(int i=1 ; i<=n ; i++)
                   ^