Submission #720134

#TimeUsernameProblemLanguageResultExecution timeMemory
720134oooRace (IOI11_race)C++14
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #include "race.h" #define ll long long const int nu = 3e5+5; typedef pair<ll, ll> cap; ll n, k, s[nu], f[nu], ans = 1e9, hh[nu]; bool r[nu]; vector< vector<cap> > g; multiset<cap> ms; int dfs(int u, int t) { s[u] = 1; for(cap x : g[u]) { int v = x.first; if(r[v] || v == t) continue; s[u] += dfs(v, u); } return s[u]; } int get_centroid(int u, int t, int sum) { for(cap x : g[u]) { int v = x.first; if(r[v] || v == t) continue; if(s[v]*2 > sum) return get_centroid(v, u, sum); } return u; } void dfs2(int u, int t, int w, int ok) { f[u] = f[t]+w; hh[u] = hh[t]+1; if(f[u] > k) return ; if(ok == 0) { cap o = {k-f[u], 0}; multiset<cap> :: iterator it; it = lower_bound(ms.begin(), ms.end(), o); if((*it).first == k-f[u]) ans = min(ans, hh[u]+(*it).second); } else ms.insert({f[u], hh[u]}); for(cap x : g[u]) { int v = x.first; ll l = x.second; if(v == t || r[v]) continue; dfs2(v, u, l, ok); } } void centroid(int u) { int cnt = dfs(u, 0); int c = get_centroid(u, 0, cnt); r[c] = true; ms.insert({0, 0}); ms.insert({1e15, 0}); for(cap x : g[c]) { int v = x.first; ll l = x.second; if(r[v]) continue; dfs2(v, 0, l, 0); dfs2(v, 0, l, 1); } while(!ms.empty()) ms.erase(*ms.begin()); for(cap x : g[c]) { int v = x.first; if(!r[v]) centroid(v); } } int best_path(int x, int y, int H[][2], int L[]) { n = x; k = y; g.resize(n+1); for(int i = 0; i < n-1; ++i) { ll u = H[i][0]; ll v = H[i][1]; ll c = L[i]; u++; v++; g[u].push_back({v, c}); g[v].push_back({u, c}); } centroid(1); return ans; }

Compilation message (stderr)

race.cpp:6:9: error: 'pair' does not name a type
    6 | typedef pair<ll, ll> cap;
      |         ^~~~
race.cpp:9:1: error: 'vector' does not name a type
    9 | vector< vector<cap> > g;
      | ^~~~~~
race.cpp:10:1: error: 'multiset' does not name a type
   10 | multiset<cap> ms;
      | ^~~~~~~~
race.cpp: In function 'int dfs(int, int)':
race.cpp:14:9: error: 'cap' was not declared in this scope
   14 |     for(cap x : g[u])
      |         ^~~
race.cpp:20:5: error: expected primary-expression before 'return'
   20 |     return s[u];
      |     ^~~~~~
race.cpp:19:6: error: expected ';' before 'return'
   19 |     }
      |      ^
      |      ;
   20 |     return s[u];
      |     ~~~~~~
race.cpp:20:5: error: expected primary-expression before 'return'
   20 |     return s[u];
      |     ^~~~~~
race.cpp:19:6: error: expected ')' before 'return'
   19 |     }
      |      ^
      |      )
   20 |     return s[u];
      |     ~~~~~~
race.cpp:14:8: note: to match this '('
   14 |     for(cap x : g[u])
      |        ^
race.cpp: In function 'int get_centroid(int, int, int)':
race.cpp:24:9: error: 'cap' was not declared in this scope
   24 |     for(cap x : g[u])
      |         ^~~
race.cpp:30:5: error: expected primary-expression before 'return'
   30 |     return u;
      |     ^~~~~~
race.cpp:29:6: error: expected ';' before 'return'
   29 |     }
      |      ^
      |      ;
   30 |     return u;
      |     ~~~~~~
race.cpp:30:5: error: expected primary-expression before 'return'
   30 |     return u;
      |     ^~~~~~
race.cpp:29:6: error: expected ')' before 'return'
   29 |     }
      |      ^
      |      )
   30 |     return u;
      |     ~~~~~~
race.cpp:24:8: note: to match this '('
   24 |     for(cap x : g[u])
      |        ^
race.cpp: In function 'void dfs2(int, int, int, int)':
race.cpp:38:9: error: 'cap' was not declared in this scope
   38 |         cap o = {k-f[u], 0};
      |         ^~~
race.cpp:39:9: error: 'multiset' was not declared in this scope; did you mean 'std::multiset'?
   39 |         multiset<cap> :: iterator it;
      |         ^~~~~~~~
      |         std::multiset
In file included from /usr/include/c++/10/set:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from race.cpp:1:
/usr/include/c++/10/bits/stl_set.h:70:11: note: 'std::multiset' declared here
   70 |     class multiset;
      |           ^~~~~~~~
race.cpp:39:26: error: '::iterator' has not been declared; did you mean 'std::iterator'?
   39 |         multiset<cap> :: iterator it;
      |                          ^~~~~~~~
      |                          std::iterator
In file included from /usr/include/c++/10/bits/stl_algobase.h:65,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from race.cpp:1:
/usr/include/c++/10/bits/stl_iterator_base_types.h:127:12: note: 'std::iterator' declared here
  127 |     struct iterator
      |            ^~~~~~~~
race.cpp:40:9: error: 'it' was not declared in this scope; did you mean 't'?
   40 |         it = lower_bound(ms.begin(), ms.end(), o);
      |         ^~
      |         t
race.cpp:40:26: error: 'ms' was not declared in this scope; did you mean 's'?
   40 |         it = lower_bound(ms.begin(), ms.end(), o);
      |                          ^~
      |                          s
race.cpp:40:48: error: 'o' was not declared in this scope
   40 |         it = lower_bound(ms.begin(), ms.end(), o);
      |                                                ^
race.cpp:40:14: error: 'lower_bound' was not declared in this scope; did you mean 'std::lower_bound'?
   40 |         it = lower_bound(ms.begin(), ms.end(), o);
      |              ^~~~~~~~~~~
      |              std::lower_bound
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from race.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:2031:5: note: 'std::lower_bound' declared here
 2031 |     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~~~
race.cpp:42:15: error: 'min' was not declared in this scope; did you mean 'std::min'?
   42 |         ans = min(ans, hh[u]+(*it).second);
      |               ^~~
      |               std::min
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from race.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: 'std::min' declared here
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
race.cpp:44:10: error: 'ms' was not declared in this scope; did you mean 's'?
   44 |     else ms.insert({f[u], hh[u]});
      |          ^~
      |          s
race.cpp:45:9: error: 'cap' was not declared in this scope
   45 |     for(cap x : g[u])
      |         ^~~
race.cpp:52:1: error: expected primary-expression before '}' token
   52 | }
      | ^
race.cpp:51:6: error: expected ';' before '}' token
   51 |     }
      |      ^
      |      ;
   52 | }
      | ~     
race.cpp:52:1: error: expected primary-expression before '}' token
   52 | }
      | ^
race.cpp:51:6: error: expected ')' before '}' token
   51 |     }
      |      ^
      |      )
   52 | }
      | ~     
race.cpp:45:8: note: to match this '('
   45 |     for(cap x : g[u])
      |        ^
race.cpp:52:1: error: expected primary-expression before '}' token
   52 | }
      | ^
race.cpp: In function 'void centroid(int)':
race.cpp:59:5: error: 'ms' was not declared in this scope; did you mean 's'?
   59 |     ms.insert({0, 0});
      |     ^~
      |     s
race.cpp:61:9: error: 'cap' was not declared in this scope
   61 |     for(cap x : g[c])
      |         ^~~
race.cpp:69:5: error: expected primary-expression before 'while'
   69 |     while(!ms.empty()) ms.erase(*ms.begin());
      |     ^~~~~
race.cpp:67:6: error: expected ';' before 'while'
   67 |     }
      |      ^
      |      ;
   68 | 
   69 |     while(!ms.empty()) ms.erase(*ms.begin());
      |     ~~~~~
race.cpp:69:5: error: expected primary-expression before 'while'
   69 |     while(!ms.empty()) ms.erase(*ms.begin());
      |     ^~~~~
race.cpp:67:6: error: expected ')' before 'while'
   67 |     }
      |      ^
      |      )
   68 | 
   69 |     while(!ms.empty()) ms.erase(*ms.begin());
      |     ~~~~~
race.cpp:61:8: note: to match this '('
   61 |     for(cap x : g[c])
      |        ^
race.cpp:70:9: error: 'cap' was not declared in this scope
   70 |     for(cap x : g[c])
      |         ^~~
race.cpp:75:1: error: expected primary-expression before '}' token
   75 | }
      | ^
race.cpp:74:6: error: expected ';' before '}' token
   74 |     }
      |      ^
      |      ;
   75 | }
      | ~     
race.cpp:75:1: error: expected primary-expression before '}' token
   75 | }
      | ^
race.cpp:74:6: error: expected ')' before '}' token
   74 |     }
      |      ^
      |      )
   75 | }
      | ~     
race.cpp:70:8: note: to match this '('
   70 |     for(cap x : g[c])
      |        ^
race.cpp:75:1: error: expected primary-expression before '}' token
   75 | }
      | ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:79:5: error: 'g' was not declared in this scope
   79 |     g.resize(n+1);
      |     ^