Submission #2337418
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
int N;
vector< vector< int > > graph;
struct CentroidPathDecomposition
{
struct Centroid
{
int ParIndex, ParDepth, Deep;
vector< int > node;
inline int size()
{
return(node.size());
}
inline int &operator[](int k)
{
return(node[k]);
}
inline pair< int, int > Up()
{
return(make_pair(ParIndex, ParDepth));
}
};
vector< int > SubTreeSize, NextPath;
vector< int > TreeIndex, TreeDepth;
vector< Centroid > Centroids;
void BuildSubTreeSize()
{
stack< pair< int, int > > s;
s.push({0, -1});
while(!s.empty()) {
auto p = s.top(); s.pop();
if(~SubTreeSize[p.first]) {
NextPath[p.first] = -1;
for(auto& to : graph[p.first]) {
if(p.second == to) continue;
SubTreeSize[p.first] += SubTreeSize[to];
if(NextPath[p.first] == -1 || SubTreeSize[NextPath[p.first]] < SubTreeSize[to]) {
NextPath[p.first] = to;
}
}
} else {
s.push(p);
SubTreeSize[p.first] = 1;
for(auto& to : graph[p.first]) {
if(p.second != to) s.push({to, p.first});
}
}
}
}
void BuildPath()
{
stack< pair< int, int > > s;
Centroids.push_back((Centroid){-1, -1, 0});
s.push({0, -1});
TreeIndex[0] = 0;
while(!s.empty()) {
auto p = s.top(); s.pop();
TreeDepth[p.first] = Centroids[TreeIndex[p.first]].size();
for(auto& to : graph[p.first]) {
if(p.second != to) {
if(to == NextPath[p.first]) { // Centroid-Path
TreeIndex[to] = TreeIndex[p.first];
} else { // Not Centroid-Path
TreeIndex[to] = Centroids.size();
Centroids.push_back((Centroid){TreeIndex[p.first], TreeDepth[p.first], Centroids[TreeIndex[p.first]].Deep + 1});
}
s.push({to, p.first});
}
}
Centroids[TreeIndex[p.first]].node.push_back(p.first);
}
}
void AddEdge(int x, int y, bool flag = false)
{
graph[x].emplace_back(y);
if(!flag) graph[y].emplace_back(x);
}
void Build()
{
BuildSubTreeSize();
BuildPath();
}
inline int size()
{
return(Centroids.size());
}
inline pair< int, int > Information(int idx)
{
return(make_pair(TreeIndex[idx], TreeDepth[idx]));
}
inline Centroid &operator[](int k)
{
return(Centroids[k]);
}
inline int LCA(int a, int b)
{
int TreeIdxA, TreeDepthA, TreeIdxB, TreeDepthB;
tie(TreeIdxA, TreeDepthA) = Information(a);
tie(TreeIdxB, TreeDepthB) = Information(b);
while(TreeIdxA != TreeIdxB) {
if(Centroids[TreeIdxA].Deep > Centroids[TreeIdxB].Deep) {
tie(TreeIdxA, TreeDepthA) = Centroids[TreeIdxA].Up();
} else {
tie(TreeIdxB, TreeDepthB) = Centroids[TreeIdxB].Up();
}
}
if(TreeDepthA > TreeDepthB) swap(TreeDepthA, TreeDepthB);
return(Centroids[TreeIdxA][TreeDepthA]);
}
CentroidPathDecomposition(int SZ)
{
graph.resize(SZ);
SubTreeSize.assign(SZ, -1);
NextPath.resize(SZ);
TreeIndex.resize(SZ);
TreeDepth.resize(SZ);
}
inline int dist(int a, int b);
};
inline int CentroidPathDecomposition::dist(int a, int b)
{
int TreeIdxA, TreeDepthA, TreeIdxB, TreeDepthB;
int ret = 0;
tie(TreeIdxA, TreeDepthA) = Information(a);
tie(TreeIdxB, TreeDepthB) = Information(b);
while(TreeIdxA != TreeIdxB) {
if(Centroids[TreeIdxA].Deep > Centroids[TreeIdxB].Deep) {
ret += TreeDepthA + 1;
tie(TreeIdxA, TreeDepthA) = Centroids[TreeIdxA].Up();
} else {
ret += TreeDepthB + 1;
tie(TreeIdxB, TreeDepthB) = Centroids[TreeIdxB].Up();
}
}
if(TreeDepthA > TreeDepthB) swap(TreeDepthA, TreeDepthB);
return(ret + TreeDepthB - TreeDepthA );
}
int main()
{
scanf("%d", &N);
CentroidPathDecomposition tree(N);
for(int i = 1; i < N; i++) {
int P;
scanf("%d", &P);
tree.AddEdge(--P, i, true);
}
tree.Build();
queue< int > que;
que.push(0);
long long ret = 0LL;
int last = 0;
while(!que.empty()) {
int p = que.front(); que.pop();
ret += tree.dist(last, p);
last = p;
for(int to : graph[p]) que.push(to);
}
printf("%lld\n", ret);
}
Submission Info
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:148:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
./Main.cpp:152:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &P);
^
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00_sample_00, 00_sample_01, 00_sample_02, 10_Random_000005_00, 10_Random_000006_04, 10_Random_000008_08, 10_Random_000033_05, 10_Random_000042_01, 10_Random_000080_09, 10_Random_000358_10, 10_Random_000463_06, 10_Random_000822_02, 10_Random_007468_03, 10_Random_013086_07, 10_Random_096889_11, 10_Random_100000_12, 10_Random_100000_13, 20_Binary_000032_00, 20_Binary_001000_01, 20_Binary_010000_02, 20_Binary_100000_03, 30_Star_100000_00, 30_Star_100000_01, 40_Skew_000023_09, 40_Skew_000031_01, 40_Skew_000043_05, 40_Skew_000044_08, 40_Skew_000046_04, 40_Skew_000047_00, 40_Skew_000354_02, 40_Skew_000539_07, 40_Skew_000814_10, 40_Skew_000853_11, 40_Skew_000935_03, 40_Skew_000951_06, 40_Skew_100000_12, 40_Skew_100000_13, 40_Skew_100000_14, 40_Skew_100000_15, 40_Skew_100000_16, 40_Skew_100000_17, 40_Skew_100000_18, 40_Skew_100000_19, 40_Skew_100000_20, 40_Skew_100000_21, 50_PowerRandom_000047_00, 50_PowerRandom_000068_04, 50_PowerRandom_000094_08, 50_PowerRandom_000126_09, 50_PowerRandom_000497_05, 50_PowerRandom_000852_01, 50_PowerRandom_008600_02, 50_PowerRandom_015225_10, 50_PowerRandom_040917_06, 50_PowerRandom_100000_03, 50_PowerRandom_100000_07, 50_PowerRandom_100000_11, 80_line_00, 81_max_ans_00, 90_teuch_00, 90_teuch_01 |
Case Name |
Status |
Exec Time |
Memory |
00_sample_00 |
AC |
1 ms |
256 KB |
00_sample_01 |
AC |
1 ms |
256 KB |
00_sample_02 |
AC |
1 ms |
256 KB |
10_Random_000005_00 |
AC |
1 ms |
256 KB |
10_Random_000006_04 |
AC |
1 ms |
256 KB |
10_Random_000008_08 |
AC |
1 ms |
256 KB |
10_Random_000033_05 |
AC |
1 ms |
256 KB |
10_Random_000042_01 |
AC |
1 ms |
256 KB |
10_Random_000080_09 |
AC |
1 ms |
256 KB |
10_Random_000358_10 |
AC |
3 ms |
256 KB |
10_Random_000463_06 |
AC |
1 ms |
256 KB |
10_Random_000822_02 |
AC |
2 ms |
384 KB |
10_Random_007468_03 |
AC |
4 ms |
896 KB |
10_Random_013086_07 |
AC |
6 ms |
1536 KB |
10_Random_096889_11 |
AC |
35 ms |
9620 KB |
10_Random_100000_12 |
AC |
36 ms |
9748 KB |
10_Random_100000_13 |
AC |
35 ms |
9748 KB |
20_Binary_000032_00 |
AC |
1 ms |
256 KB |
20_Binary_001000_01 |
AC |
1 ms |
384 KB |
20_Binary_010000_02 |
AC |
4 ms |
1280 KB |
20_Binary_100000_03 |
AC |
35 ms |
9488 KB |
30_Star_100000_00 |
AC |
25 ms |
12016 KB |
30_Star_100000_01 |
AC |
25 ms |
12016 KB |
40_Skew_000023_09 |
AC |
1 ms |
256 KB |
40_Skew_000031_01 |
AC |
1 ms |
256 KB |
40_Skew_000043_05 |
AC |
1 ms |
256 KB |
40_Skew_000044_08 |
AC |
1 ms |
256 KB |
40_Skew_000046_04 |
AC |
1 ms |
256 KB |
40_Skew_000047_00 |
AC |
1 ms |
256 KB |
40_Skew_000354_02 |
AC |
1 ms |
256 KB |
40_Skew_000539_07 |
AC |
1 ms |
256 KB |
40_Skew_000814_10 |
AC |
1 ms |
384 KB |
40_Skew_000853_11 |
AC |
1 ms |
256 KB |
40_Skew_000935_03 |
AC |
1 ms |
384 KB |
40_Skew_000951_06 |
AC |
1 ms |
384 KB |
40_Skew_100000_12 |
AC |
27 ms |
8144 KB |
40_Skew_100000_13 |
AC |
26 ms |
8216 KB |
40_Skew_100000_14 |
AC |
36 ms |
9492 KB |
40_Skew_100000_15 |
AC |
36 ms |
9492 KB |
40_Skew_100000_16 |
AC |
35 ms |
10384 KB |
40_Skew_100000_17 |
AC |
34 ms |
9796 KB |
40_Skew_100000_18 |
AC |
34 ms |
13968 KB |
40_Skew_100000_19 |
AC |
30 ms |
12192 KB |
40_Skew_100000_20 |
AC |
36 ms |
9492 KB |
40_Skew_100000_21 |
AC |
27 ms |
8284 KB |
50_PowerRandom_000047_00 |
AC |
1 ms |
256 KB |
50_PowerRandom_000068_04 |
AC |
1 ms |
256 KB |
50_PowerRandom_000094_08 |
AC |
1 ms |
256 KB |
50_PowerRandom_000126_09 |
AC |
1 ms |
256 KB |
50_PowerRandom_000497_05 |
AC |
1 ms |
256 KB |
50_PowerRandom_000852_01 |
AC |
1 ms |
384 KB |
50_PowerRandom_008600_02 |
AC |
4 ms |
1152 KB |
50_PowerRandom_015225_10 |
AC |
6 ms |
1884 KB |
50_PowerRandom_040917_06 |
AC |
14 ms |
4372 KB |
50_PowerRandom_100000_03 |
AC |
37 ms |
9872 KB |
50_PowerRandom_100000_07 |
AC |
35 ms |
13968 KB |
50_PowerRandom_100000_11 |
AC |
35 ms |
12432 KB |
80_line_00 |
AC |
26 ms |
8064 KB |
81_max_ans_00 |
AC |
26 ms |
7856 KB |
90_teuch_00 |
AC |
1 ms |
256 KB |
90_teuch_01 |
AC |
1 ms |
256 KB |