답안 #494678

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
494678 2021-12-16T01:52:07 Z avaneeshk098 Birokracija (COCI18_birokracija) C++17
50 / 100
1000 ms 23224 KB
#include <bits/stdc++.h>
#pragma GCC optimize "trapv"

#define ff              first
#define int 			long long int
#define ss              second
#define pb              push_back
#define mp              make_pair
#define mt              make_tuple
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define max_size        100000000
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define mod             (int)1e9+7
#define w(t)			int t; cin >> t; while(t--)
#define inf             1e18
//#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define range(a,b)      substr(a,b-a+1)
#define mina(a,b,c)		min(a, min(b, c))
#define maxa(a,b,c)		max(a, max(b, c))
#define sz(a)			(int)a.size()	
#define endl 			'\n'
#define trace(x)        cerr<<#x<<": "<<x<<" "<<endl;
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define FOR(x,y)		for(int i = x; i < y; i++)
#define rrep(a,b,x,y)	for(int x = 0; x < a; x++) for(int y = 0; y < b; y++)
#define rrep1(a,b,x,y)	for(int x = 1; x <= a; x++) for(int y = 0; y <= b; y++)
#define rrepo(a,b,x,y)	for(int x = 0; x < a; x++){ for(int y = 0; y < b; y++)
#define rrepo1(a,b,x,y)	for(int x = 1; x <= a; x++){ for(int y = 0; y <= b; y++)

	
using namespace std;

bool sortbysecond(const pair<int,int> &a, const pair<int,int> &b){ return (a.second < b.second); } 

int64_t ceil_div(int64_t a, int64_t b) {if(a%b != 0){ return ((a/b)+1);} else{ return (a/b);}}

double max(double a, double b){ if(a >= b){ return a; } else{ return b; } }

double min(double a, double b){if(a <= b){return a;} else{return b;	}}

bool modd(double a, double b){if(floor(a/b) == ceil(a/b)){return true;} return false;}

bool stringsort(const string &a, const string &b){return a.length() > b.length();}

bool specsort(const pair<long double,int> &a, const pair<long double,int> &b){ 
	return a.first - a.second > b.first - b.second;  
}

struct ufds{
	vi link, siz;
	int cmp;
	ufds(int n) : link(n), siz(n,1) { iota(link.begin(), link.end(), 0); cmp = n;}
	int find(int x){
		if(x == link[x]) return x;
		return link[x] = find(link[x]);
	}
	
	bool same(int x, int y){
		return find(x) == find(y);
	}
	
	bool unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return false;
		if(x < y) swap(x,y);
		siz[x] += siz[y];
		link[y] = x;
		cmp--;
		return true;
	}
	
	int components(){
		return cmp;
	}
	
	bool size(int x){ 
		return siz[link[x]];
	}
};

struct segtree{
	vi a;
	vector<pii> seg;
	int siz;
	segtree(int n, vi &b) : seg(4*n) { a = b; }
	
	pii combine(pii c, pii b){
		if(c.first < b.first) return c;
		else if(c.first > b.first) return b;
		return {c.first, c.second + b.second};
	}
	
	void build(int l, int r, int pos){
		if(l == r){ // if l == r it means it is a laef node so only 1 minimum
			seg[pos].first = a[l];
			seg[pos].second = 1;
			return;
		}
		int mid = (l+r)/2;
		build(l,mid, pos*2); // filling left tree for minimum
		build(mid+1, r, pos*2+1); // filling right tree for minimum
		seg[pos] = combine(seg[pos*2], seg[pos*2+1]);
	}
	
	pii query(int l, int r, int ql, int qr, int pos){
		if(l > qr || r < ql) return {inf, inf};
		if(l >= ql && r <= qr) return seg[pos];
		int mid = (l+r)/2;
		pii q1 = query(l, mid, ql, qr, pos*2);
		pii q2 = query(mid+1, r, ql, qr, pos*2 + 1);
		int val = min(q1.first, q2.first);
		if(q1.first == q2.first){
			return {val, q1.second + q2.second};
		}
		else if(val == q1.first){
			return {val, q1.second};
		}
		else if(val == q2.first){
			return {val, q2.second};
		}
	}
	
	void update(int l, int r, int p, int x, int pos){
		if(l == r){
			seg[pos].first = x;
			seg[pos].second = 1;
			return;
		}
		int mid = (l+r)/2;
		if(p <= mid){
			update(l, mid, p, x, pos*2);
		}
		else{
			update(mid+1, r, p , x, pos*2 + 1);
		}
		seg[pos] = combine(seg[pos*2], seg[pos*2+1]);
	}
};

int child;
int level = 1;

void dfs(int u, vi &visited, vector<set<int>> &adj, vi &score){
	visited[u] = 1;
	int next = inf;
	for(auto v : adj[u]) next = min(next, v);
	if(next != inf && !visited[next]){
		dfs(next, visited, adj, score);
		adj[u].erase(child);
		level++;
		score[u] += level;
	}
	if(next == inf){
		score[u]++;
		child = u;
		level = 1;
		return;
	}
}

void solve(){	
	int n;
	cin >> n;
	vector<set<int>> adj(n+1);
	for(int i = 2; i <= n; i++){
		int k;
		cin >> k;
		adj[k].insert(i);
	}
	vi visited(n+1);
	vi score(n+1);
	while((int)adj[1].size() != 0){
		dfs(1, visited, adj, score);
		for(int i = 0; i < n; i++) visited[i] = 0; 
	}
	dfs(1, visited, adj, score);
	for(auto i : score){
		if(i != 0) cout << i << " ";
	}
	cout << endl;
}

int32_t main(){
	FIO;
	//w(t){solve();}
	solve();
    return 0; 
}
	
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 216 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 372 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 364 KB Output is correct
2 Correct 9 ms 468 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1071 ms 2512 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1066 ms 8364 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1032 ms 23208 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1074 ms 23224 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1062 ms 22724 KB Time limit exceeded
2 Halted 0 ms 0 KB -