Submission #197767

#	Time	Username	Problem	Language	Result	Execution time	Memory
197767		heon	Birokracija (COCI18_birokracija)	C++17	100 / 100	135 ms	29436 KiB

birokracija

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10