Submission #1679958


Source Code Expand

#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<unordered_map>
using namespace std;
//---------------------------------------------------
//ライブラリゾーン!!!!
//#define int long long
#define str string
#define rep(i,j) for(int i=0;i<(int)(j);i++)
typedef long long ll;
typedef long double ld;
const ll inf = 4523372036854775807;
short gh[2][4] = { { 0,0,-1,1 },{ -1,1,0,0 } };
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {//隣接リスト表現
	ll to, cost;
};
struct S {//辺の情報を入れる変数
	int from, to, cost;
};
struct H {
	int x, y;
};
bool operator<(H a, H b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
bool operator>(H a, H b) {
	if (a.x != b.x) return a.x > b.x;
	return a.y > b.y;
}
ll gcm(ll i, ll j) {//最大公約数
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcm(j%i, i);
}
ld rad(ld a, ld b, ld c, ld d) {
	return sqrt(pow(a - c, 2) + pow(b - d, 2));
}//rad=座標上の2点間の距離
int ari(int a, int b, int c) {
	return (a + b)*c / 2;
}//等差数列の和
bool suf(ld a, ld b, ld c, ld d) {
	if (b <= c || d <= a) return 0;
	return 1;
}//[a,b),[c,d)
//---------------------------------------------------
//+++++++++++++++++++++++++++++++++++++++++++++++++++
int n, u, pa[100000], b[100000];
vector<int>e[100000];
H a[100000];
signed main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		cin >> u;
		e[u].push_back(i);
		e[i].push_back(u);
	}
	queue<int>q;
	q.push(0);
	while (!q.empty()) {
		int t = q.front(); q.pop();
		for (int i = 0; i < e[t].size(); i++) {
			if (e[t][i] != pa[t]) {
				pa[e[t][i]] = t;
				q.push(e[t][i]);
				a[e[t][i]] = H{ a[t].y,e[t][i] };
			}
		}
	}
	sort(a, a + n);
	for (int i = n - 1; i > 0; i--)
		b[pa[i]] +=  b[i] + 1;
	for (int i = 0; i < n; i++) {
		int sum = 0;
		if (i != 0)
			sum = b[0] - b[i];
		for (int j = 0; j < e[i].size(); j++) {
			if (e[i][j] != pa[i])
				sum = max(sum, b[e[i][j]]+1);
		}
		cout << sum << endl;
	}
	getchar(); getchar();
}

Submission Info

Submission Time
Task C - 高橋王国の分割統治
User Thistle
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2338 Byte
Status AC
Exec Time 239 ms
Memory 8320 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 3 ms 2560 KB
sample_02.txt AC 3 ms 2560 KB
subtask1_01.txt AC 3 ms 2560 KB
subtask1_02.txt AC 3 ms 2560 KB
subtask1_03.txt AC 3 ms 2560 KB
subtask1_04.txt AC 2 ms 2560 KB
subtask1_05.txt AC 4 ms 2688 KB
subtask1_06.txt AC 4 ms 2688 KB
subtask1_07.txt AC 4 ms 2688 KB
subtask1_08.txt AC 4 ms 2688 KB
subtask1_09.txt AC 4 ms 2688 KB
subtask2_01.txt AC 166 ms 6528 KB
subtask2_02.txt AC 204 ms 7552 KB
subtask2_03.txt AC 239 ms 8064 KB
subtask2_04.txt AC 219 ms 8064 KB
subtask2_05.txt AC 181 ms 8312 KB
subtask2_06.txt AC 184 ms 8320 KB
subtask2_07.txt AC 194 ms 7808 KB