Submission #3789307


Source Code Expand

#include <bits/stdc++.h>
#define FOR(v, a, b) for(int v = (a); v < (b); ++v)
#define FORE(v, a, b) for(int v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(int v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define LLI long long int
using namespace std;
template <typename T> using V = vector<T>;
template <typename T, typename U> using P = pair<T,U>;
template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
vector<vector<int>> tree;
vector<int> s, m, p;

int dfs(int cur, int par){
  p[cur] = par;
  s[cur] = 1;

  for(auto next : tree[cur]){
    if(next == par) continue;
    int t = dfs(next, cur);

    s[cur] += t;
    m[cur] = max(m[cur], t);
  }
  
  return s[cur];
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N; cin >> N;

  tree = vector<vector<int>>(N);
  s = vector<int>(N);
  m = vector<int>(N);
  p = vector<int>(N);

  FORE(i,1,N-1){
    int p; cin >> p;
    tree[i].push_back(p);
    tree[p].push_back(i);
  }

  dfs(0,-1);

  //join(cerr, ALL(s));
  //join(cerr, ALL(m));
  //join(cerr, ALL(p));

  REP(i,N){
    int ans = m[i];
    if(p[i] != -1) ans = max(ans, N-s[i]);
    cout << ans << endl;
  }
  
  return 0;
}

Submission Info

Submission Time
Task C - 高橋王国の分割統治
User you070707
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1443 Byte
Status AC
Exec Time 182 ms
Memory 13696 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 2
AC × 11
AC × 18
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
Subtask1 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt
Subtask2 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 3 ms 384 KB
subtask1_06.txt AC 3 ms 384 KB
subtask1_07.txt AC 3 ms 384 KB
subtask1_08.txt AC 3 ms 384 KB
subtask1_09.txt AC 3 ms 384 KB
subtask2_01.txt AC 132 ms 5632 KB
subtask2_02.txt AC 159 ms 7040 KB
subtask2_03.txt AC 181 ms 7552 KB
subtask2_04.txt AC 182 ms 7552 KB
subtask2_05.txt AC 166 ms 7928 KB
subtask2_06.txt AC 163 ms 8064 KB
subtask2_07.txt AC 173 ms 13696 KB