| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 666567 | si_jo | Race (IOI11_race) | C++14 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define pbds tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
#define ll long long
//#define int ll
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define all(x) (x).begin(), (x).end()
#define uniq(v) (v).erase(unique(all(v)), (v).end())
#define sz(x) (int)((x).size())
#define fr first
#define sc second
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define rep(i,a,b) for(int i = a; i < b; i++)
#define irep(i, a, b) for(int i = a; i > b; i--)
#define mem1(a) memset(a, -1, sizeof(a))
#define mem0(a) memset(a, 0, sizeof(a))
#define clz __builtin_clzll //leading zeroes
#define ctz __builtin_ctzll //trailing zeroes
#define ppc __builtin_popcountll
#define nl cout << '\n'
const ll INF = 1e18;
const int32_t M = 1e9 + 7;
const int32_t MM = 998244353;
const int MAX = numeric_limits<int>::max();
const int MIN = numeric_limits<int>::min();
// const int N = 0;
int N, K, H[200010][2], L[200010];
int n, ans, k;
vi s, d, undo;
map<pii, int> wt;
void getsize(int cur, int par, vector<set<int>>& adj){
s[cur] = 1;
for(int a : adj[cur]) if(a != par){
getsize(a, cur, adj);
s[cur] += s[a];
}
}
int centre(int cur, int par, vector<set<int>>& adj, int tot){
for(int a : adj[cur]) if(a != par && s[a] > tot / 2) return centre(a, cur, adj, tot);
return cur;
}
void count(int cur, int par, vector<set<int>>& adj, bool f, int depth, int len){
if(len > k) return;
if(f) d[len] = min(d[len], depth);
else ans = min(ans, depth + d[k - len]);
for(int a : adj[cur]) if(a != par) count(a, cur, adj, f, depth + 1, len + wt[{a, cur}]);
}
void centroid(int cur, int par, vector<set<int>>& adj){
getsize(cur, par, adj);
int c = centre(cur, par, adj, s[cur]);
for(int a : adj[c]){
count(a, c, adj, 0, 1, wt[{a, c}]);
count(a, c, adj, 1, 1, wt[{a, c}]);
}
ans = min(ans, d[k]);
for(int i : undo) d[i] = 1e9;
undo.clear();
for(int a : adj[c]){
adj[a].erase(c);
centroid(a, c, adj);
}
}
void best_path(int N, int K, int H[][2], int L[]){
n = N, k = K; s.resize(n + 1); d.assign(k + 1, 1e9);
ans = n;
vvi h(n - 1, vi(2)); cin >> h;
vector<set<int>> adj(n + 1);
rep(i, 0, n - 1){
int u = H[i][0] + 1, v = H[i][1] + 1;
adj[u].insert(v); adj[v].insert(u);
wt[{u, v}] = wt[{v, u}] = L[i];
}
centroid(1, 0, adj);
cout << (ans == n ? -1 : ans); nl;
}
Compilation message (stderr)
race.cpp:81:6: error: ambiguating new declaration of 'void best_path(int, int, int (*)[2], int*)'
81 | void best_path(int N, int K, int H[][2], int L[]){
| ^~~~~~~~~
In file included from race.cpp:1:
race.h:1:5: note: old declaration 'int best_path(int, int, int (*)[2], int*)'
1 | int best_path(int N, int K, int H[][2], int L[]);
| ^~~~~~~~~
race.cpp: In function 'void best_path(int, int, int (*)[2], int*)':
race.cpp:84:27: error: no match for 'operator>>' (operand types are 'std::istream' {aka 'std::basic_istream<char>'} and 'std::vector<std::vector<int> >')
84 | vvi h(n - 1, vi(2)); cin >> h;
| ~~~ ^~ ~
| | |
| | std::vector<std::vector<int> >
| std::istream {aka std::basic_istream<char>}
In file included 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:2:
/usr/include/c++/10/istream:120:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>::__istream_type& (*)(std::basic_istream<_CharT, _Traits>::__istream_type&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]'
120 | operator>>(__istream_type& (*__pf)(__istream_type&))
| ^~~~~~~~
/usr/include/c++/10/istream:120:36: note: no known conversion for argument 1 from 'std::vector<std::vector<int> >' to 'std::basic_istream<char>::__istream_type& (*)(std::basic_istream<char>::__istream_type&)' {aka 'std::basic_istream<char>& (*)(std::basic_istream<char>&)'}
120 | operator>>(__istream_type& (*__pf)(__istream_type&))
| ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/istream:124:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>::__ios_type& (*)(std::basic_istream<_CharT, _Traits>::__ios_type&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>; std::basic_istream<_CharT, _Traits>::__ios_type = std::basic_ios<char>]'
124 | operator>>(__ios_type& (*__pf)(__ios_type&))
| ^~~~~~~~
/usr/include/c++/10/istream:124:32: note: no known conversion for argument 1 from 'std::vector<std::vector<int> >' to 'std::basic_istream<char>::__ios_type& (*)(std::basic_istream<char>::__ios_type&)' {aka 'std::basic_ios<char>& (*)(std::basic_ios<char>&)'}
124 | operator>>(__ios_type& (*__pf)(__ios_type&))
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
/usr/include/c++/10/istream:131:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::ios_base& (*)(std::ios_base&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]'
131 | operator>>(ios_base& (*__pf)(ios_base&))
| ^~~~~~~~
/usr/include/c++/10/istream:131:30: note: no known conversion for argument 1 from 'std::vector<std::vector<int> >' to 'std::ios_base& (*)(std::ios_base&)'
131 | operator>>(ios_base& (*__pf)(ios_base&))
| ~~~~~~~~~~~~^~~~~~~~~~~~~~~~
/usr/include/c++/10/istream:168:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(bool&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]'
168 | operator>>(bool& __n)
| ^~~~~~~~
/usr/include/c++/10/istream:168:24: note: no known conversion for argument 1 from 'std::vector<std::vector<int> >' to 'bool&'
168 | operator>>(bool& __n)
| ~~~~~~^~~
/usr/include/c++/10/istream:172:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(short int&) [with _CharT = char; _Traits = std::char_traits<char>]'
172 | operator>>(short& __n);
| ^~~~~~~~
/usr/include/c++/10/istream:172:25: note: no known conversion for argument 1 from 'std::vector<std::vector<int> >' to 'short int&'
172 | operator>>(short& __n);
| ~~~~~~~^~~
/usr/include/c++/10/istream:175:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(short unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]'
175 | operator>>(unsigned short& __n)
| ^~~~~~~~
/usr/include/c++/10/istream:175:34: note: no known conversion for argument 1 from 'std::vector<std::vector<int> >' to 'short unsigned int&'
175 | operator>>(unsigned short& __n)
| ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/istream:179:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(int&) [with _CharT = char; _Traits = std::char_traits<char>]'
179 | operator>>(int& __n);
| ^~~~~~~~
/usr/include/c++/10/istream:179:23: note: no known conversion for argument 1 from 'std::vector<std::vector<int> >' to 'int&'
179 | operator>>(int& __n);
| ~~~~~^~~
/usr/include/c++/10/istream:182:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]'
182 | operator>>(unsigned int& __n)
| ^~~~~~~~
/usr/include/c++/10/istream:182:32: note: no known conversion for argument 1 from 'std::vector<std::vector<int> >' to 'unsigned int&'
182 | operator>>(unsigned int& __n)
| ~~~~~~~~~~~~~~^~~
/usr/include/c++/10/istream:186:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]'
186 | operator>>(long& __n)
| ^~~~~~~~
/usr/include/c++/10/istream:186:24: note: no known conversion for argument 1 from 'std::vector<std::vector<int> >' to 'long int&'
186 | operator>>(long& __n)
| ~~~~~~^~~
/usr/include/c++/10/istream:190:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]'
190 | operator>>(unsigned long& __n)
| ^~~~~~~~
/usr/include/c++/10/istream:190:33: note: no known conversion for argument 1 from 'std::vector<std::vector<int> >' to 'long unsigned int&'
190 | operator>>(unsigned long& __n)
| ~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/istream:195:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]'
195 | operator>>(long long& __n)
| ^~~~~~~~
/usr/include/c++/10/istream:195:29: note: no known conversion for argument 1 from 'std::vector<std::vector<int> >' to 'long long int&'
195 | operator>>(long long& __n)
| ~~~~~~~~~~~^~~
/usr/include/c++/10/istream:199:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]'
199 | operator>>(unsigned long long& __n)
| ^~~~~~~~
/usr/include/c++/10/istream:199:38: note: no known conversion for argument 1 from 'std::vector<std::vector<int> >' to 'long long unsigned int&'
199 | operator>>(unsigned long long& __n)
| ~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/istream:214:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(float&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]'
214 | operator>>(float& __f)
| ^~~~~~~~
/usr/include/c++/10/istream:214:25: note: no known conversion for argument 1 from 'std::vector<std::vector<int> >' to 'float&'
214 | operator>>(float& __f)
| ~~~~~~~^~~
/usr/include/c++/10/istream:218:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(double&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]'
218 | operator>>(double& __f)
| ^~~~~~~~
/usr/include/c++/10/istream:218:26: note: no known conversion for argument 1 from 'std::vector<std::vector<int> >' to 'double&'
218 | operator>>(double& __f)
| ~~~~~~~~^~~
/usr/include/c++/10/istream:222:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long double&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]'
222 | operator>>(long double& __f)
| ^~~~~~~~
/usr/include/c++/10/istream:222:31: note: no known conversion for argument 1 from 'std::vector<std::vector<int> >' to 'long double&'
222 | operator>>(long double& __f)
| ~~~~~~~~~~~~~^~~
/usr/include/c++/10/istream:235:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(void*&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]'
235 | operator>>(void*& __p)
| ^~~~~~~~
/usr/include/c++/10/istream:235:25: note: no known conversion for argument 1 from 'std::vector<std::vector<int> >' to 'void*&'
235 | operator>>(void*& __p)
| ~~~~~~~^~~
/usr/include/c++/10/istream:259:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>::__streambuf_type*) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__streambuf_type = std::basic_streambuf<char>]'
259 | operator>>(__streambuf_type* __sb);
| ^~~~~~~~
/usr/include/c++/10/istream:259:36: note: no known conversion for argument 1 from 'std::vector<std::vector<int> >' to 'std::basic_istream<char>::__streambuf_type*' {aka 'std::basic_streambuf<char>*'}
259 | operator>>(__streambuf_type* __sb);
| ~~~~~~~~~~~~~~~~~~^~~~
In file included from /usr/include/c++/10/string:56,
from /usr/include/c++/10/bits/locale_classes.h:40,
from /usr/include/c++/10/bits/ios_base.h:41,
from /usr/include/c++/10/ios:42,
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:2:
/usr/include/c++/10/bits/basic_string.tcc:1476:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::basic_istream<_CharT, _Traits>& std::operator>>(std::basic_istream<_CharT, _Traits>&, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)'
1476 | operator>>(basic_istream<_CharT, _Traits>& __in,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.tcc:1476:5: note: template argument deduction/substitution failed:
race.cpp:84:30: note: 'std::vector<std::vector<int> >' is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
84 | vvi h(n - 1, vi(2)); cin >> h;
| ^
In file included from /usr/include/c++/10/istream:991,
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:2:
/usr/include/c++/10/bits/istream.tcc:931:5: note: candidate: 'template<class _CharT, class _Traits> std::basic_istream<_CharT, _Traits>& std::operator>>(std::basic_istream<_CharT, _Traits>&, _CharT&)'
931 | operator>>(basic_istream<_CharT, _Traits>& __in, _CharT& __c)
| ^~~~~~~~
/usr/include/c++/10/bits/istream.tcc:931:5: note: template argument deduction/substitution failed:
race.cpp:84:30: note: deduced conflicting types for parameter '_CharT' ('char' and 'std::vector<std::vector<int> >')
84 | vvi h(n - 1, vi(2)); cin >> h;
| ^
In file included 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:2:
/usr/include/c++/10/istream:756:5: note: candidate: 'template<class _Traits> std::basic_istream<char, _Traits>& std::operator>>(std::basic_istream<char, _Traits>&, unsigned char&)'
756 | operator>>(basic_istream<char, _Traits>& __in, unsigned char& __c)
| ^~~~~~~~
/usr/include/c++/10/istream:756:5: note: template argument deduction/substitution failed:
race.cpp:84:30: note: cannot convert 'h' (type 'std::vector<std::vector<int> >') to type 'unsigned char&'
84 | vvi h(n - 1, vi(2)); cin >> h;
| ^
In file included 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:2:
/usr/include/c++/10/istream:761:5: note: candidate: 'template<class _Traits> std::basic_istream<char, _Traits>& std::operator>>(std::basic_istream<char, _Traits>&, signed char&)'
761 | operator>>(basic_istream<char, _Traits>& __in, signed char& __c)
| ^~~~~~~~
/usr/include/c++/10/istream:761:5: note: template argument deduction/substitution failed:
race.cpp:84:30: note: cannot convert 'h' (type 'std::vector<std::vector<int> >') to type 'signed char&'
84 | vvi h(n - 1, vi(2)); cin >> h;
| ^
In file included from /usr/include/c++/10/istream:991,
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:2:
/usr/include/c++/10/bits/istream.tcc:963:5: note: candidate: 'template<class _CharT2, class _Traits2> std::basic_istream<_CharT, _Traits>& std::operator>>(std::basic_istream<_CharT, _Traits>&, _CharT2*)'
963 | operator>>(basic_istream<_CharT, _Traits>& __in, _CharT* __s)
| ^~~~~~~~
/usr/include/c++/10/bits/istream.tcc:963:5: note: template argument deduction/substitution failed:
race.cpp:84:30: note: mismatched types '_CharT2*' and 'std::vector<std::vector<int> >'
84 | vvi h(n - 1, vi(2)); cin >> h;
| ^
In file included 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:2:
/usr/include/c++/10/istream:803:5: note: candidate: 'template<class _Traits> std::basic_istream<char, _Traits>& std::operator>>(std::basic_istream<char, _Traits>&, unsigned char*)'
803 | operator>>(basic_istream<char, _Traits>& __in, unsigned char* __s)
| ^~~~~~~~
/usr/include/c++/10/istream:803:5: note: template argument deduction/substitution failed:
race.cpp:84:30: note: cannot convert 'h' (type 'std::vector<std::vector<int> >') to type 'unsigned char*'
84 | vvi h(n - 1, vi(2)); cin >> h;
| ^
In file included 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:2:
/usr/include/c++/10/istream:808:5: note: candidate: 'template<class _Traits> std::basic_istream<char, _Traits>& std::operator>>(std::basic_istream<char, _Traits>&, signed char*)'
808 | operator>>(basic_istream<char, _Traits>& __in, signed char* __s)
| ^~~~~~~~
/usr/include/c++/10/istream:808:5: note: template argument deduction/substitution failed:
race.cpp:84:30: note: cannot convert 'h' (type 'std::vector<std::vector<int> >') to type 'signed char*'
84 | vvi h(n - 1, vi(2)); cin >> h;
| ^
In file included 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:2:
/usr/include/c++/10/istream:980:5: note: candidate: 'template<class _Istream, class _Tp> typename std::enable_if<std::__and_<std::__not_<std::is_lvalue_reference<_Tp> >, std::__is_convertible_to_basic_istream<_Istream>, std::__is_extractable<typename std::__is_convertible_to_basic_istream<_Tp>::__istream_type, _Tp&&, void> >::value, typename std::__is_convertible_to_basic_istream<_Tp>::__istream_type>::type std::operator>>(_Istream&&, _Tp&&)'
980 | operator>>(_Istream&& __is, _Tp&& __x)
| ^~~~~~~~
/usr/include/c++/10/istream:980:5: note: template argument deduction/substitution failed:
/usr/include/c++/10/istream: In substitution of 'template<class _Istream, class _Tp> typename std::enable_if<std::__and_<std::__not_<std::is_lvalue_reference<_Tp> >, std::__is_convertible_to_basic_istream<_Istream>, std::__is_extractable<typename std::__is_convertible_to_basic_istream<_Tp>::__istream_type, _Tp&&, void> >::value, typename std::__is_convertible_to_basic_istream<_Tp>: