oj.uz

Submission #197767

# Submission time Handle Problem Language Result Execution time Memory
197767 2020-01-22T22:05:48 Z heon Birokracija (COCI18_birokracija) C++17
100 / 100
 135 ms 29436 KB 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <iomanip>
using namespace std;
#define all(x) x.begin(), x.end()
typedef vector <int> vi;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;
int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }
int sub(int a, int b) { return (a -= b) < 0 ? a + mod : a; }
int ctz(int x) { return __builtin_ctz(x); }
int clz(int x) { return __builtin_clz(x); }

const int maxn = 2e5 + 5;
vi g[maxn];
ll dp[maxn];
int sz[maxn];

void dfs(int u, int p){
  sz[u] = dp[u] = 1;
  for(int v : g[u]){
    if(v != p){
      dfs(v, u);
      dp[u] += dp[v];
      sz[u] += sz[v];
      dp[u] += sz[v];
    }
  }
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  #ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif

  int n;
  cin >> n;
  for(int i = 2; i <= n; i++){
    int u;
    cin >> u;
    g[i].push_back(u);
    g[u].push_back(i);
  }
  dfs(1, 1);
  for(int u = 1; u <= n; u++){
    cout << dp[u] << " ";
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5368 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5096 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 7 ms 5020 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6140 KB Output is correct
2 Correct 15 ms 6532 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 8772 KB Output is correct
2 Correct 34 ms 8824 KB Output is correct
3 Correct 33 ms 10104 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 15608 KB Output is correct
2 Correct 85 ms 17288 KB Output is correct
3 Correct 87 ms 29436 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 15544 KB Output is correct
2 Correct 86 ms 16132 KB Output is correct
3 Correct 84 ms 18612 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 15224 KB Output is correct
2 Correct 84 ms 16540 KB Output is correct
3 Correct 82 ms 20916 KB Output is correct