Submission #1073882
Source Code Expand
#ifndef __clang__
#pragma GCC optimize "-O3"
#pragma GCC target "tune=native"
#endif
#ifdef ONLINE_JUDGE
#define NDEBUG 1
#endif
#include <stdio.h>
#include <bits/stdc++.h>
#define DESTRUCT2(p, a, b) \
auto a = get<0>(p); \
auto b = get<1>(p);
#define DESTRUCT3(p, a, b, c) \
auto a = get<0>(p); \
auto b = get<1>(p); \
auto c = get<2>(p);
#define DESTRUCT4(p, a, b, c, d) \
auto a = get<0>(p); \
auto b = get<1>(p); \
auto c = get<2>(p); \
auto d = get<3>(p);
#define FOR(i, n) for(lli i = 0; i < (lli)(n); ++i)
#define FORU(i, j, k) for(lli i = (j); i <= (lli)(k); ++i)
#define FORD(i, j, k) for(lli i = (j); i >= (lli)(k); --i)
#define SQ(x) ((x)*(x))
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
using namespace std;
template<typename... As>
struct tpl : public std::tuple<As...> {
using std::tuple<As...>::tuple;
template<typename T = tuple<As...> >
typename tuple_element<0, T>::type const&
x() const { return get<0>(*this); }
template<typename T = tuple<As...> >
typename tuple_element<0, T>::type&
x() { return get<0>(*this); }
template<typename T = tuple<As...> >
typename tuple_element<1, T>::type const&
y() const { return get<1>(*this); }
template<typename T = tuple<As...> >
typename tuple_element<1, T>::type&
y() { return get<1>(*this); }
template<typename T = tuple<As...> >
typename tuple_element<2, T>::type const&
z() const { return get<2>(*this); }
template<typename T = tuple<As...> >
typename tuple_element<2, T>::type&
z() { return get<2>(*this); }
template<typename T = tuple<As...> >
typename tuple_element<3, T>::type const&
w() const { return get<3>(*this); }
template<typename T = tuple<As...> >
typename tuple_element<3, T>::type&
w() { return get<3>(*this); }
};
using lli = long long int;
using llu = long long unsigned;
using pii = tpl<lli, lli>;
using piii = tpl<lli, lli, lli>;
using piiii = tpl<lli, lli, lli, lli>;
using vi = vector<lli>;
using vii = vector<pii>;
using viii = vector<piii>;
using vvi = vector<vi>;
using vvii = vector<vii>;
using vviii = vector<viii>;
template<class T>
using min_queue = priority_queue<T, vector<T>, greater<T> >;
template<class T>
using max_queue = priority_queue<T>;
template<size_t... I>
struct my_index_sequence {
using type = my_index_sequence;
static constexpr array<size_t, sizeof...(I)> value = { {I...} };
};
namespace my_index_sequence_detail {
template<typename I, typename J> struct concat;
template<size_t... I, size_t... J>
struct concat<my_index_sequence<I...>, my_index_sequence<J...> > :
my_index_sequence<I..., (sizeof...(I)+J)...> { };
template<size_t N> struct make_index_sequence :
concat<typename make_index_sequence<N/2>::type, typename make_index_sequence<N-N/2>::type>::type { };
template <> struct make_index_sequence<0> : my_index_sequence<>{};
template <> struct make_index_sequence<1> : my_index_sequence<0>{};
}
template<class... A>
using my_index_sequence_for = typename my_index_sequence_detail::make_index_sequence<sizeof...(A)>::type;
template<class T, size_t... I>
void print_tuple(ostream& s, T const& a, my_index_sequence<I...>){
using swallow = int[];
(void)swallow{0, (void(s << (I == 0? "" : ", ") << get<I>(a)), 0)...};
}
template<class T>
ostream& print_collection(ostream& s, T const& a);
template<class... A>
ostream& operator<<(ostream& s, tpl<A...> const& a);
template<class... A>
ostream& operator<<(ostream& s, tuple<A...> const& a);
template<class A, class B>
ostream& operator<<(ostream& s, pair<A, B> const& a);
template<class T, size_t I>
ostream& operator<<(ostream& s, array<T, I> const& a) { return print_collection(s, a); }
template<class T>
ostream& operator<<(ostream& s, vector<T> const& a) { return print_collection(s, a); }
template<class T, class U>
ostream& operator<<(ostream& s, multimap<T, U> const& a) { return print_collection(s, a); }
template<class T>
ostream& operator<<(ostream& s, multiset<T> const& a) { return print_collection(s, a); }
template<class T, class U>
ostream& operator<<(ostream& s, map<T, U> const& a) { return print_collection(s, a); }
template<class T>
ostream& operator<<(ostream& s, set<T> const& a) { return print_collection(s, a); }
template<class T>
ostream& print_collection(ostream& s, T const& a){
s << '[';
for(auto it = begin(a); it != end(a); ++it){
s << *it;
if(it != prev(end(a))) s << " ";
}
return s << ']';
}
template<class... A>
ostream& operator<<(ostream& s, tpl<A...> const& a){
s << '(';
print_tuple(s, a, my_index_sequence_for<A...>{});
return s << ')';
}
template<class... A>
ostream& operator<<(ostream& s, tuple<A...> const& a){
s << '(';
print_tuple(s, a, my_index_sequence_for<A...>{});
return s << ')';
}
template<class A, class B>
ostream& operator<<(ostream& s, pair<A, B> const& a){
return s << "(" << get<0>(a) << ", " << get<1>(a) << ")";
}
namespace std {
namespace {
template <class T>
inline void hash_combine(size_t& seed, T const& v) {
seed ^= hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
template <class Tuple, size_t Index = tuple_size<Tuple>::value - 1>
struct HashValueImpl {
static void apply(size_t& seed, Tuple const& tuple) {
HashValueImpl<Tuple, Index-1>::apply(seed, tuple);
hash_combine(seed, get<Index>(tuple));
}
};
template <class Tuple>
struct HashValueImpl<Tuple, 0> {
static void apply(size_t& seed, Tuple const& tuple) {
hash_combine(seed, get<0>(tuple));
}
};
}
template <typename ... TT>
struct hash<tuple<TT...>> {
size_t operator()(tuple<TT...> const& tt) const {
size_t seed = 0;
HashValueImpl<tuple<TT...> >::apply(seed, tt);
return seed;
}
};
template <typename ... TT>
struct hash<tpl<TT...>> {
size_t operator()(tpl<TT...> const& tt) const {
size_t seed = 0;
HashValueImpl<tuple<TT...> >::apply(seed, tt);
return seed;
}
};
}
lli read_positive(){
char c; lli x=0;
do { c = getchar(); } while(c<'0' || c>'9');
while(c>='0'&&c<='9') {
x=10*x+(c-'0');
c = getchar();
}
return x;
}
//------------------------------------------------------------------------------
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
vvi G(n);
FOR(i,n-1) {
int a; cin >> a; --a;
G[a].pb(i+1);
}
vi D(n);
function<void(int)> dfs = [&](int i) {
vi b;
for(int j : G[i]) {
dfs(j);
b.pb(D[j]);
}
sort(all(b));
FOR(j,b.size()) {
D[i] = max<lli>(D[i], b[j]+b.size()-j);
}
};
dfs(0);
cout << D[0] << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Tournament |
User |
Rafbill |
Language |
C++14 (GCC 5.4.1) |
Score |
800 |
Code Size |
7219 Byte |
Status |
AC |
Exec Time |
41 ms |
Memory |
19200 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
800 / 800 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt, s3.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, s1.txt, s2.txt, s3.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
AC |
32 ms |
5248 KB |
02.txt |
AC |
31 ms |
5248 KB |
03.txt |
AC |
35 ms |
5248 KB |
04.txt |
AC |
31 ms |
5248 KB |
05.txt |
AC |
31 ms |
5248 KB |
06.txt |
AC |
31 ms |
5248 KB |
07.txt |
AC |
34 ms |
5376 KB |
08.txt |
AC |
31 ms |
5248 KB |
09.txt |
AC |
31 ms |
5248 KB |
10.txt |
AC |
31 ms |
5248 KB |
11.txt |
AC |
41 ms |
19200 KB |
12.txt |
AC |
37 ms |
14592 KB |
13.txt |
AC |
35 ms |
12416 KB |
14.txt |
AC |
35 ms |
10112 KB |
15.txt |
AC |
32 ms |
8576 KB |
16.txt |
AC |
31 ms |
7280 KB |
17.txt |
AC |
30 ms |
6400 KB |
18.txt |
AC |
29 ms |
5760 KB |
19.txt |
AC |
30 ms |
5632 KB |
20.txt |
AC |
30 ms |
5504 KB |
21.txt |
AC |
17 ms |
5748 KB |
22.txt |
AC |
17 ms |
5100 KB |
23.txt |
AC |
18 ms |
4904 KB |
24.txt |
AC |
17 ms |
4652 KB |
25.txt |
AC |
15 ms |
4608 KB |
26.txt |
AC |
16 ms |
4480 KB |
27.txt |
AC |
16 ms |
4352 KB |
28.txt |
AC |
16 ms |
4480 KB |
29.txt |
AC |
17 ms |
4608 KB |
30.txt |
AC |
18 ms |
4480 KB |
31.txt |
AC |
26 ms |
4992 KB |
32.txt |
AC |
27 ms |
5120 KB |
33.txt |
AC |
23 ms |
4608 KB |
34.txt |
AC |
23 ms |
4736 KB |
35.txt |
AC |
22 ms |
4992 KB |
36.txt |
AC |
19 ms |
4224 KB |
37.txt |
AC |
18 ms |
4224 KB |
38.txt |
AC |
17 ms |
4352 KB |
39.txt |
AC |
15 ms |
4352 KB |
40.txt |
AC |
15 ms |
4224 KB |
41.txt |
AC |
2 ms |
256 KB |
42.txt |
AC |
3 ms |
256 KB |
43.txt |
AC |
3 ms |
256 KB |
44.txt |
AC |
2 ms |
256 KB |
45.txt |
AC |
3 ms |
256 KB |
46.txt |
AC |
3 ms |
256 KB |
47.txt |
AC |
3 ms |
256 KB |
48.txt |
AC |
3 ms |
256 KB |
49.txt |
AC |
3 ms |
256 KB |
50.txt |
AC |
3 ms |
256 KB |
s1.txt |
AC |
3 ms |
256 KB |
s2.txt |
AC |
3 ms |
256 KB |
s3.txt |
AC |
3 ms |
256 KB |